当前位置：首页 > news >正文

动态规划-状态压缩、树形DP问题总结

news 来源：原创 2024/4/29 10:34:02

什么是动态规划

动态规划通过额外的空间将已经搜索过的相似的结果（指某些具有相同性质解的集合）用一个数组存起来，所以DP中的状态转移看上去是某两三个值之间的推导，其实是某两三个集合之间的状态转移！

状态压缩DP

蒙德里安的梦想

典型题例：

求把 N×M 的棋盘分割成若干个 1×2 的长方形，有多少种方案。
例如当 N=2，M=4 时，共有 5 种方案。当 N=2，M=3 时，共有 3 种方案。

示例：

输入：
输入包含多组测试用例。
每组测试用例占一行，包含两个整数 N 和 M。
当输入用例 N=0，M=0 时，表示输入终止，且该用例无需处理
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0
输出：
1
0
1
2
3
5
144
51205

思路
核心：先放横着得，再放竖着得
总方案数：等于只放横着得小方块得合法方案数。
如何判断当前方案是否合法？
答：所有剩余位置，能否充满竖着得小方块；可以按列来看，每一列内部所有连续得空着的小方块需要偶数个
状态表示：集合集合f[i,j]表示已经将前i-1列摆好，且从第i-1列伸出到第i列的状态j的所有方案。（化零为整）

状态计算：集合划分总共有2^n中状态；Σf[i-1,k],其中k为二进制数。（化整为零）
需要注意的是f[i-1,k]要与f[i,j]构成合法的方案，需要满足的条件：
1.j与 k 不能再同一行，即(j & k == 0)
2. 所有的连续空着的位置的长度必须是偶数
边界：f[0,0]=1
答案：f[m,0];

代码：

include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 12, M = 1 << N;  //M = 2^n
typedef long long LL;

int n, m;
LL f[N][M];
vector<int> state[M];  //二维数组记录合法状态；写法等价：vector<vector<int>> state(M)
bool st[M];  //存储每种状态是否有奇数个连续的0，如果奇数个0是无效状态，如果是偶数个零置为true。

int main() {
    
    while (cin >> n >> m, n || m) { 读入n和m，并且不是两个0即合法输入就继续读入
    
        //预处理，对应满足条件2
        for (int i = 0; i < 1 << n; i ++) {
            
            int cnt = 0;  //记录连续0的个数
            bool is_valid = true;  //某种状合法（不存在连续奇数个0）
            
            for (int j = 0; j < n; j ++) {
                if ((i >> j) & 1) {  //状态i的二进制数的第j位
                    if (cnt & 1) { //又伸出来的，则看前面连续0的个数是奇数则不合法
                        is_valid = false; 
                        break;
                    }
                    cnt = 0;  //前面的是合法的了，计数器可以清零
                }
                else cnt ++;  //该位置还是0,增加计数
            }
            if (cnt & 1) is_valid = false;  //最后一段判断下是否合法
            st[i] = is_valid;  //是否合法状体保存再st中
        }
        
        //预处理，对应满足条件1
        for (int i = 0; i < 1 << n; i ++) {
            state[i].clear();
            
            for (int j = 0; j < 1 << n; j ++) 
                if ((i & j) == 0 && st[i | j]) 
                    state[i].push_back(j);
        }
        
        //dp开始
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        
        for (int i = 1; i <= m; i ++) 
            for (int j = 0; j < 1 << n; j ++)  //遍历第i列所有状态
                for (auto k : state[j])  //遍历i-1列状态k,合法转移
                    f[i][j] += f[i - 1][k];
        
        cout << f[m][0] << endl;
    }
    return 0;
}

树形DP问题

没有上司的舞会

典型题例：

Ural 大学有 N 名职员，编号为 1∼N。
他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。
每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。
现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。
在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

示例：

输入：
第一行一个整数 N。
接下来 N 行，第 i 行表示 i 号职员的快乐指数 Hi。
接下来 N−1 行，每行输入一对整数 L,K，表示 K 是 L 的直接上司。。
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出：
5

思路
等价于完全背包问题：有一个容量为n的背包，且有n个物品，对应的体积分别为1~n,恰好装满背包的方案数
状态表示：集合f[u,0]表示所有从以u为根得子树中选择，并且不选择u这个点得方案
集合f[u,1]表示所有从以 u 为根得子树中选择，并且选择u这个点得方案
状态计算：f[u,0] += Σ max(f[si,0]+f[si,1]) 其中si表示父节点u得每个孩子节点
f[u,1] = Σ f[si,0] 父节点选了，孩子节点就不能选了
答案为两个集合的最大值

代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 6010;

int n;
int enjoy[N];
int h[N], e[N], ne[N], idx;  //邻接表
bool has_father[N];  //是否有父节点
int f[N][N];

int add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u) {
    
    f[u][1] = enjoy[u];  //选择u则先加上u的高姓度
    
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        dfs(j);
        //两个集合的求法 
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}  

int main() {
    
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++)  scanf("%d", &enjoy[i]);
    
    memset(h, -1, sizeof h);
    
    for (int i = 1; i < n; i ++) {
        int x, y;
        scanf("%d%d", &x, &y);
        has_father[x] = true;  //y是x的father
        add(y, x);
    }
    
    int root = 1;
    while (has_father[root]) root ++;  //找到root节点
    
    dfs(root);  
    
    printf("%d\n", max(f[root][0], f[root][1]));
    return 0;
}