树形DP

Echidna · 2020-09-21 21:36:37 · 个人记录

其中j为i的子节点，s_k为k的学分，t为分给j的子树的学习机会次数，并且明显1 \le t \le j 。

没看懂？没问题

为什么呢？我们为了求以i为根节点的子树、有j个学习机会的最大学分，必然会把这些学分分给每一个子树。所以就有了这个奇妙的转移方程。

现在我们回顾这个方程，发现为了求出f[i][j]，我们需要先知道f[k][t]。很明显，t \le i，所以问题规模是在不断缩小的。为了求出f[k][t]，我们又要去找k的子节点……

貌似还有一个问题：叶结点怎么办？叶结点只有两种状态：学或者不学。当学的时候，f[i][1]=s_i ；不学的时候，f[i][0]=0

这样的话，我们就能写一个用dfs实现的dp了 （有点怪）

这道题还有一个小技巧可以使用。因为数据是个森林（有多棵树），直接dp还得涉及数据的合并，非常难搞，我们可以假设每一门没有先修课的科目的先修课都是0，这样就把一个森林变成了一棵树。（ 《 生 物 科 技 》 ）

下面是代码:

#include<iostream>
#include<cstring>
using namespace std;
const int N=310;
int f[N][N];    //这个是DP数组
int h[N];       //i的学分
struct side{
    int t,n;
};
side ss[N];     //链式前向星存图
int head[N];
int k=1;
void add(int f,int t){
    ss[k].t=t;
    ss[k].n=head[f];
    head[f]=k++;
}
int n,m;        //分别代表科目的数量，可以修的课的数量
void dp(int k){     //用dfs实现的dp
    f[k][1]=h[k];           //不管怎么样，如果只选一门课，那只能选自己。         
    for(int nxt=head[k];nxt!=-1;nxt=ss[nxt].n){     //枚举每一个子节点
        int to=ss[nxt].t;
        dp(to);                 //因为要知道f[to][i],所以要先递归到to上，算出f[to]
        for(int j=m;j>=1;j--)       //枚举总的学习机会
            for(int i=j-1;i>=1;i--)     //枚举分给to的学习机会。
                f[k][j]=max(f[k][j],f[k][j-i]+f[to][i]);
        //因为这里实际上使用了滚动数组优化法，所以j一定要倒序枚举，否则在使用之前覆盖之前算出的得数。
   }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<=n+1;i++)
        head[i]=-1;
    for(int a,b,i=1;i<=n;i++){
        cin>>a;
        add(a,i);
        cin>>h[i];
    }
    m++;
    dp(0);          //为了方便，我们假设0为所有没有父节点的根节点
    cout<<f[0][m]<<endl;
    return orz;
}

P1352 没有上司的舞会

这道题大概的意思就是如果一个人的上司参与了舞会的话，他就不会参与，否则反之。每一个人都有一个逗比 （弱智） 指数，请你编程计算如何安排可以让这个舞会的逗比指数最大。

首先按照上一个题说的技巧，我们可以快速地设f[i][j]为以第i个人为根的子树， 然后还是需要具体题目具体分析。

我们可以设f[i][j]为第i个人参加或者不参加的时候舞会上有的最大的逗比指数，j=0代表不参加，j=1代表参加。

如果这个人参加的话，那么他的下属都不会参加，所以我们需要把所有下属不参加的最大的逗比指数加起来，也就是\sum_{j \in son[i]}f[j][0] ；同时我们还要把这个人参加所增加的逗比指数加进去，总的状态转移方程就是这样的：

f[i][1]=v_i+\sum_{j \in son[i]}f[j][0]，其中 v_i 代表i的逗比指数，son[i] 代表第i个人的下属的集合。

如果这个人不参加的话，那么他的下属有可能参加或者不参加，但他的逗比值不会加到舞会里。

所以总的状态转移方程是这样的：

f[i][0]=\sum_{j \in son[i]} max(f[j][0],f[j][1]) , 其中son[i] 代表第i个人的下属的集合。

对于这个题目，小的细节问题就是我们不清楚哪个人是老板（树的跟）。对此，我们可以在输入的时候统计每一个人的入度，如果这个人的入度为零，说明这个人是这个公司的老板，记为root。

分析到这里，其实题目的状态转移方程就已经出来了，剩下的就是套模板，用dfs的方式去完成dp。在每一个节点，计算这个人的f[i][0]、f[i][1]。最后dp完成之后输出max\{f[root][1],f[root][0]\} 即可。

代码：

#include<iostream>
using namespace std;
const int N=6e3+100;
int h[N];
int f[N][2];
int n;
struct node{
    int t,n;
}nodes[N];
int head[N];
int k=1;
void add(int f,int t){
    nodes[k].t=t;
    nodes[k].n=head[f];
    head[f]=k++;
}
int rd[N];
int root;
void dp(int k){
    f[k][0]=0;
    f[k][1]=h[k];
    int nxt=head[k];
    while(nxt!=0){
        int y=nodes[nxt].t;
        dp(y);
        f[k][0]+=max(f[y][0],f[y][1]);
        f[k][1]+=f[y][0];
        nxt=nodes[nxt].n; 
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>h[i];
    for(int a,b,i=1;i<n;i++){
        cin>>a>>b;
        rd[a]++;
        add(b,a);
    }
    for(int i=1;i<=n;i++)
        if(rd[i]==0){
            root=i;break;
        }
    dp(root);
    cout<<max(f[root][0],f[root][1])<<endl;
    return orz;
}

P1272 重建道路

这道题的基本意思就是：John的农场的道路被地震摧毁了，重建后形成了一个树状结构， John非常开心 ，并想让你计算如果再来一场地震，震出来一个有m个节点的联通块的最少的需要摧毁的道路是多少。

感觉这么说还是搞不懂啊，那就看看数据吧。

输入数据:input_1        输出数据:output_1
11 6            2
1 2                     
1 3                     
1 4                     
1 5                     
2 6                     
2 7                     
2 8                     
4 9                     
4 10                    
4 11                    

那么我们来看看这个题的数据：要求形成一个有六个点的独立联通块。现在看着这个图，然后我们就可以找规律了。如果我们找1,2,3,4,5,6这六个点的话，那么我们就要断开五条边（2\rightarrow7 , 2\rightarrow8 ,1\rightarrow3 , 1\rightarrow4 , 1\rightarrow5）才能让1,2,3,4,5,6变成一个独立联通块

如果我们选择 1,2,3,6,7,8 这6个点的话，我们只需要断开两条边就行了（1\rightarrow4 , 1\rightarrow5），这显然是正解（为什么呢？看看输出就知道了）。

如果实在还不了解题意的可以去看看这道题的题解 （太懒了）

我们仍然可以套树形DP的模板：设f[i][j]。i可以意思是以i为根节点的子树，但是j应该代表什么呢？我们看看这道题的未知数： 断开的路的数量 和 最多形成的最大独立联通块的大小 。咦？正好是两个量，那么一个是j 、一个是f[i][j]不就行了吗？还真是这样。

因为我们最终要求的是这棵树形成一个有m个节点的独立联通块的最小断掉的路的数量，所以如果设j为断掉的路的数量，不是很好写转移方程；如果设 f[i][j] 为断掉的路的数量，就会好写很多。 (这一段看得懂看不懂都无所谓。)

下面开始转移方程的推导。

对于一个有n个节点的子树，很明显最多可以断开n-1条边，不能再多了（没边可以拆了）。我们设 f[i][j] 为对于以i为根节点的子树，形成j的联通块所需要的最少的删边数量。我们需要分别考虑每一个子节点。

我们的思路就是父节点有j次删边的机会，我们就把这些机会分给j的子节点，然后看怎么分需要删的边最少，所以我们的转移方程就像这样：

这样点3就推完了。

根据这个方法，我们可以推出来任何一个点往上和往下推k层经过节点的和。

验证了思路的正确性，我们可以开始想DP了。（其实写题的时候是先写出来的DP，在想出来的往上推的方式）

我们容易得出：

其中 “ \prod ” 为连乘号，也就是把它后面连着的全部乘起来。

那么为什么是这个状态转移方程呢？假如这个节点有两个子节点，那么只要这两个子节点的颜色不和父节点重合，它们之间没有任何关系和影响。所以这里满足乘法原则：做一件事，完成它需要分成n个步骤，做第一 步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法。那么完成这件事共有 N=m1×m2×m3×…×mn 种不同的方法。

但是呢，对于每一个节点，它选择了一种颜色它就不能选择其他的颜色。这里就满足加法原则了：做一件事情，完成它有n类方式，第一类方式有M1种方法，第二类方式有M2种方法，……，第n类方式有Mn种方法，那么完成这件事情共有M1+M2+……+Mn种方法。

现在我们弄懂了如果子节点没有已经涂颜色的点的时候状态转移方程的推法。现在考虑其他的问题：如果这个点的子节点有已经被涂颜色了呢？很明显，这时我们不能把这个点的颜色涂成跟这个点的颜色是一样的。状态转移方程其实完全没有改变：我们设集合K为这个点可以选择的颜色，如果你要涂的颜色不在K中，那么我们就把这个颜色的f设为零。

说句人话就是：不让涂我就留0。

这个问题解决了之后，还有最后一个分问题：如果这个点是已经被涂了颜色的点，怎么办？

我们设这个点的颜色是c，那么如果这个点已经被涂了颜色的话，很明显，K=\{c\}，也就是说，我们对于这个点只能选择涂c颜色。那么我们要不要直接粗暴的把这个状态转移方程的值赋为0或者1呢？

不能这样做。我可以画一个图，解释一下这种情况怎么做。

尽管红点的两个子节点的父节点是已经被染了色的点，我们仍然有四种染色的方案。如果我们直接把红点的dp的值写成1或者0的话，这会和正解不一样。

所以如果这个点已经被染色了，那么状态转移方程会是这样的：

所以这和上边的方程有区别吗？

有区别。区别就是除了c其他的颜色都是0。

如果您还是不能理解的话，您可以对照一下样例的图和dp数组的值自行理解。

dp数组的值：

            4 4 0
            1 1 1
            1 1 1
            0 0 1

树状数组实在是累死了，这篇博客到这里一应该结束了，后续可能不会更新了。

接下来我可能会去学线段树、数位DP、状压DP、斜率优化DP之类的数据结构和算法。

最后骗一波赞

这篇博客中有些题是我在做完好多天之后才写的，对于一些题的印象可能不是很深了，如果有错误和疏忽还请指出，感激不尽！