The more, The Better

Time Limit: 6000/2000 MS ( Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4684 Accepted Submission(s): 2766

Problem Description ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？

Input 每个测试实例首先包括2个整数，N,M.(1 <= M <= N <= 200);在接下来的N行里，每行包括2个整数，a,b. 在第 i 行，a 代表要攻克第 i 个城堡必须先攻克第 a 个城堡，如果 a = 0 则代表可以直接攻克第 i 个城堡。b 代表第 i 个城堡的宝物数量, b >= 0。当N = 0, M = 0输入结束。
Output 对于每个测试实例，输出一个整数，代表ACboy攻克M个城堡所获得的最多宝物的数量。
Sample Input

Sample Output

5
13

题意：中文题，很好懂的。
思路：树形dp，容易想到状态 dp[i][j] i-在哪个点 j-攻克城堡的个数（必须攻克自己） dp-获得的最大宝物数 dp[i][1]=该点宝物数

有方程 dp[i][j]=max(dp[i][j],dp[son][k]+dp[i][j-k]);
可以将0号点也看做树上的一点，或者单独处理也行，我按前者处理的。开始我这样写一直不对，一直跟踪状态转移，发现是这个原因： 0号点是虚拟的，不需要占攻克次数，所以对0号点处理时dp[0][0]是合法状态。
代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
         #include 
         
           #include 
          
            #include 
           
             #include 
            
              #pragma comment (linker,"/STACK:102400000,102400000") #define maxn 205 #define MAXN 1005 #define mod 1000000009 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 1e-6 typedef long long ll; using namespace std; int n,m,k,ans,cnt,tot,flag; int pp[maxn],cost[maxn],dp[maxn][maxn]; struct Node { int v,w,next; } edge[MAXN]; void addedge(int u,int v,int w) { cnt++; edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=pp[u]; pp[u]=cnt; } void dfs(int u) { int i,j,v,t; dp[u][1]=cost[u]; for(i=pp[u]; i; i=edge[i].next) { v=edge[i].v; dfs(v); for(j=m; j>=0; j--) { t=0; for(k=0; k<=j-(u!=0); k++) { t=max(t,dp[v][k]+dp[u][j-k]); } dp[u][j]=max(dp[u][j],t); } } } int main() { int i,j,t,u; while(scanf("%d%d",&n,&m),n|m) { cnt=0; memset(pp,0,sizeof(pp)); for(i=1; i<=n; i++) { scanf("%d%d",&u,&cost[i]); addedge(u,i,0); } memset(dp,0,sizeof(dp)); dfs(0); ans=dp[0][m]; printf("%d\n",ans); } return 0; }

hdu 1561 The more, The Better (树形dp)

The more, The Better