poj1155 poj2468 树形DP专题。 - c++编程基础

e 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 input
Each test case contains three parts.
The first part is two numbers N K, whose meanings we have talked about just now. We denote the nodes by 1 2 ... N. Since it is a tree, each node can reach any other in only one route. (1<=N<=100, 0<=K<=200)
The second part contains N integers (All integers are nonnegative and not bigger than 1000). The ith number is the amount of apples in Node i.
The third part contains N-1 line. There are two numbers A,B in each line, meaning that Node A and Node B are adjacent.
Input will be ended by the end of file.

Note: Wshxzt starts at Node 1.

Output

For each test case, output the maximal numbers of apples Wshxzt can eat at a line.

Sample Input

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]);

【代码】

#include
  
   
#include
   
     #include
    
      using namespace std; const int maxn=100+5; int num[maxn],map[maxn][maxn],data[maxn],f[maxn][maxn*2][2]; bool visit[maxn]; int n,i,step,x,y; void dp(int k) { visit[k]=true; int i; for (i=0;i<=step;i++) f[k][i][0]=data[k]; for (i=0;i<=step;i++) f[k][i][1]=data[k]; for (i=1;i<=num[k];i++) { int go=map[k][i]; if (visit[go]) continue; dp(go); for (int run=step;run>=0;run--) for (int down=0;down<=run;down++) { f[k][run+2][0]=max(f[k][run+2][0],f[go][down][0]+f[k][run-down][0]); f[k][run+1][1]=max(f[k][run+1][1],f[go][down][1]+f[k][run-down][0]); f[k][run+2][1]=max(f[k][run+2][1],f[go][down][0]+f[k][run-down][1]); } } } int main() { while (scanf("%ld%ld",&n,&step)!=EOF) { memset(num,0,sizeof(num)); memset(map,0,sizeof(map)); memset(f,0,sizeof(f)); memset(visit,0,sizeof(visit)); for (i=1;i<=n;i++) scanf("%ld",&data[i]); for (i=1;i
     
      【后记】细节坑死人！第二个程序原来DP的第二重循环down的终值我原来写成step了，就一直过不了~~

poj1155 poj2468 树形DP专题。(二)