【序言】樹形DP一直不太會。趁著練DP的時候，寫了兩道樹形的背包。鑒於這塊知識非常不熟練，網上參考了一點題解。為了加強記憶，特寫此題解。
【題目1】
TELE Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3445 Accepted: 1781Description
A TV-network plans to broadcast an important football match. Their network of transmitters and users can be represented as a tree. The root of the tree is a transmitter that emits the football match, the leaves of the tree are the potential users and other vertices in the tree are relays (transmitters).Input
The first line of the input file contains two integers N and M, 2 <= N <= 3000, 1 <= M <= N-1, the number of vertices in the tree and the number of potential users.Output
The first and the only line of the output file should contain the maximal number of users described in the above text.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
Croatia OI 2002 Final Exam - Second Day【大意】一棵樹中有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; }
Apple Tree Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6762 Accepted: 2242
Description
Wshxzt is a lovely girl. She likes apple very much. One day HX takes her to an apple tree. There are N nodes in the tree. Each node has an amount of apples. Wshxzt starts her happy trip at one node. She can eat up all the apples in the nodes she reaches. HX is a kind guy. He knows that eating too many can make the lovely girl become fat. So he doesn’t allow Wshxzt to go more than K steps in the tree. It costs one step when she goes from one node to another adjacent node. Wshxzt likes apple very much. So she wants to eat as many as she can. Can you tell how many apples she can eat in at most K steps.Input
There are several test cases in the inputOutput
For each test case, output the maximal numbers of apples Wshxzt can eat at a line.Sample Input
2 1 0 11 1 2 3 2 0 1 2 1 2 1 3
Sample Output
11 2
Source
POJ Contest,Author:magicpig@ZSU【分析】原來以為很水，用f[i][j]表示到第i個節點，走了j步的最大值。但是很快就發現這樣有點問題。往上一看，原來還要再加一維,f[i][j][0]表示必須最後回到根節點，f[i][j][1]表示不必（當然也可以）回到根節點。
方程似乎很麻煩。
①0的狀態：下去再上來，走兩步。f[k][run+2][0]=max(f[k][run+2][0],f[go][down][0]+f[k][run-down][0]);
②1的狀態
1、直接下去。f[k][run+1][1]=max(f[k][run+1][1],f[go][down][1]+f[k][run-down][0]);
2、也可以再上來。f[k][run+2][1]=max(f[k][run+2][1],f[go][down][0]+f[k][run-down][1]);
【代碼】
