poj1155 poj2468 树形DP专题。(一)

【序言】树形DP一直不太会。趁着练DP的时候，写了两道树形的背包。鉴于这块知识非常不熟练，网上参考了一点题解。为了加强记忆，特写此题解。

【题目1】

Description

Input

Output

Sample Input

9 6
3 2 2 3 2 9 3
2 4 2 5 2
3 6 2 7 2 8 2
4 3 3 3 1 1

Sample Output

5

Source

【大意】一棵树中有N个节点，编号是最后M个的节点是叶节点。每条边会有一个花费。你从1号点（根节点）开始，如果到达某个叶节点，你就能获得它的权值，但要付出所经过的边的花费。在你获得的利润S>=0的情况下，要求所到达的叶节点尽量的多。

【分析】用f[i][j]表示到i节点，以i为根的子树中到达j个的最大利润。输出时倒着循环枚举，如果f[1][ans]大于等于0就可行。下面研究状态转移方程。以前我一直以为这种选择最优解的题目要把多叉树转化为二叉树，后来发现其实并不用。我们依次枚举每一个孩子。f[k][now]=max(f[k][now],f[k][now-cut]+f[go][cut]-a[i].s);其中now是枚举当前我所在的根的状态，而cut则是给某个孩子的j值。而a[i].s就是边权。

【注意】①点多，建议开边表。

②运算时可能会有负数，一开始初始化时要赋成负无穷大。

【代码】

#include
  
   
#include
   
     using namespace std; const int maxn=3500+5; const int INF=2100000000; struct arr{int r,s,next;}a[maxn]; int num[maxn],ok[maxn],begin[maxn],end[maxn],f[maxn][maxn]; int n,m,x,b,c,i,j,ans,cnt; void make_up(int u,int v,int s) { a[++cnt].r=v;a[cnt].s=s; if (begin[u]==0) {begin[u]=cnt;end[u]=cnt;} else {a[end[u]].next=cnt;end[u]=cnt;} } void dp(int k) { if (k>=n-m+1) { f[k][1]=num[k];ok[k]=1; return; } int i=begin[k]; while (i) { int go=a[i].r; dp(go); ok[k]+=ok[go]; for (int now=ok[k];now>0;now--) for (int cut=0;cut<=ok[go];cut++) f[k][now]=max(f[k][now],f[k][now-cut]+f[go][cut]-a[i].s); i=a[i].next; } } int main() { scanf("%ld%ld",&n,&m); for (i=1;i<=n;i++) for (j=1;j<=m;j++) f[i][j]=-INF; for (i=1;i<=n-m;i++) { scanf("%ld",&x); while (x) { scanf("%ld%ld",&b,&c); make_up(i,b,c);x--; } } for (i=n-m+1;i<=n;i++) scanf("%ld",&num[i]); dp(1); for (ans=m;ans>=0;ans--) if (f[1][ans]>=0) {printf("%ld",ans);break;} return 0; }
   
  

Description