树形动规

顾名思义, 树形动态规划就是在“树”的数据结构上的动态规划. 在树上面做动态规划是很常见的, 因为树上的一些问题是符合动态规划的条件的.

• 递归性与重叠子问题: 树的每一个节点的拓扑结构都类似, 因此每个节点的决策都可以用统一的方法完成.
• 无后效性: 当某个节点的状态已经确立, 将不会影响其子节点的状态. 也就是说, 子树间的决策是互不影响的.
  比如说这道题是典型的树形dp, 如果我们只记录一维的话, 我们会无从得知上司有没有去, 所以我们需要记录二维.

比如dp[u][go], 若go == 1, 则说明u去了舞会;
若go == 0, 则说明u没有去舞会.
若u去了舞会, 那么他的直系下属将都不能去舞会;
若u没有去舞会, 那么他的直系下属可以去舞会.

这样我们可以简单的写出一个记忆化搜索的程序, 通过入度关系找到根.

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
const int MAXN = 6600;
using namespace std;
int n;
int happy[MAXN], indegree[MAXN];
int dp[2][MAXN];// 二维的位置写反了, 调了半天, 我记得明明那么写的啊
struct Edge{
    int to, next;
} edges[MAXN];
int edgeCnt, ihead[MAXN];
void insert(int u, int v){
    Edge & e = edges[++edgeCnt];
    e.to = v;
    e.next = ihead[u];
    ihead[u] = edgeCnt;
}
int getMax(int u, int go){
    if(dp[go][u] != 0x3f3f3f3f){
        return dp[go][u];
    }
    int & rst = dp[go][u];
    rst = 0;
    // int rst = 0;
    if(go){
        rst += happy[u];
        for(int i = ihead[u]; i; i = edges[i].next){
            Edge & e = edges[i];
            rst += getMax(e.to, 0);
        }
    }
    else{
        for(int i = ihead[u]; i; i = edges[i].next){
            Edge & e = edges[i];
            rst += max(getMax(e.to, 0), getMax(e.to, 1));
        }
    }
    return dp[go][u] = rst;
}
int main(){
    memset(dp, 0x3f, sizeof(dp));

    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", happy + i);
    }
    int u, v;
    for(int i = 0; i < n; ++i){
        scanf("%d%d", &v, &u);
        insert(u, v);
        ++indegree[v];
    }
    int root;
    for(int i = 1; i <= n; ++i){
        if(indegree[i] == 0){
            root = i;
        }
    }
    printf("%d\n", max(getMax(root, 0), getMax(root, 1)));
    return 0;
}

我发现memset(dp, -0x3f, sizeof(dp)这句话, 并不能使dp数组的值成为-0x3f3f3f3f.