【CTSC1997】选课

树形dp可能是最优美的dp了……

这是一道经典的树上背包问题，考虑两种做法。第一种是直接在树上做一遍背包问题，另一种是把这棵树转化成“左儿子右兄弟”的二叉树，再做一遍背包问题。

方法一：我们定义f[i][j]表示以i为根的子树，一共选j门课最大的分数，那么我们可以得到f[i][j]=max(f[i][j-k]+f[x][k]) 其中x∈son(i).将这棵树遍历一遍即可求解。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 using namespace std;
 6 int n,m,s[310];
 7 vector<int> a[310];
 8 int f[310][310];
 9 void dfs(int now) {
10     f[now][0]=0;
11     for(int i=0;i<a[now].size();i++) {
12         int to=a[now][i];
13         dfs(to);
14         for(int j=m;j>=0;j--)
15             for(int k=j;k>=0;k--)
16                 f[now][j]=max(f[now][j],f[now][j-k]+f[to][k]);
17     }
18     if(now) {
19         for(int i=m;i>=1;i--) 
20             f[now][i]=f[now][i-1]+s[now];
21     }
22 }
23 int main() {
24     cin>>n>>m;
25     for(int i=1,x;i<=n;i++) {
26         cin>>x>>s[i];
27         a[x].push_back(i);
28     }
29     memset(f,0xcf,sizeof(f));
30     dfs(0);
31     cout<<f[0][m]<<endl;
32     return 0;
33 }

AC Code 1

方法二：将这棵树转化为“左儿子右兄弟”的二叉树，此时f[i][j]表示在新的二叉树当中，f[i][j]表示以i为根的子树，一共选j门课最大的分数。那么分两种情况讨论。

如果不选i，那么i的左儿子（原来的树中的儿子）就不能选，此时f[i][j]=f[brother[i]][j].
如果选i,并且选了k个i的左儿子，那么f[i][j]=val[i]+f[son[i]][k]+f[brother[i]][j-k-1].

我们在这两种决策当中取最优即可。

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 template <typename T>
 5 T max(T x,T y)
 6 {
 7     return x>y?x:y;
 8 }
 9 inline int read() {
10     int ret=0,f=1;
11     char c=getchar();
12     while(c<'0'||c>'9') {
13         if(c=='-') f=-1;
14         c=getchar();
15     }
16     while(c<='9'&&c>='0') {
17         ret=ret*10+c-'0';
18         c=getchar();
19     }
20     return ret*f;
21 }
22 int n,m,so[310],br[310];
23 int f[310][310],val[310];
24 inline void add(int father,int son) {
25     br[son]=so[father];
26     so[father]=son;
27 }
28 int dfs(int i,int j) {
29     if(i==-1) return 0;
30     if(j==0) return 0;
31     if(f[i][j]!=-1) return f[i][j];
32     int ret=-1<<30;
33     ret=max(ret,dfs(br[i],j));
34     for(int k=0;k<=j-1;k++)
35         ret=max(ret,dfs(so[i],k)+dfs(br[i],j-k-1)+val[i]);
36     return f[i][j]=ret;
37 }
38 int main() {
39     n=read(); m=read();
40     memset(so,-1,sizeof(so));
41     memset(br,-1,sizeof(br));
42     memset(f,-1,sizeof(f));
43     for(int i=1;i<=n;i++) {
44         int x;
45         x=read();
46         val[i]=read();
47         add(x,i);
48     }
49     printf("%d
",dfs(0,m+1));
50     return 0;
51 }

AC Code 2