HDU1011树形DP+DFS - c++编程基础

/*
	自己的第一道树形DP题
	 
	HDU1011题意：
	深搜+树形DP
	为了阐述的简便，先解释输入数据
	输入n和m，n为定点数，m为人数
	之后n行为cost[i]，score[i]分别为第i点需要耗费的体力和可以得到的分数
	之后n-1行为构造树，规定了1点为树根
	读到-1 -1结束

	下面解释cost，score
	每个人有20点体力值，在每个点可以分配人数，当人数*20>=cost[i]时，可以得到第i点的score[i]
	但是每个人最多分配在一个点上

	求最多得到的分数

	思路：构数之后DP
	为叶子结点时，判断当前还剩的人数能否得到该点的分数return (20*剩下的人数>=cost[i])?score[i]:0
	
	参考了大神kuangbin的代码，十分感谢 
*/ 
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
       #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             using namespace std; #define input freopen("input.txt","r",stdin); #define output freopen("output.txt","w",stdout); #define For1(i,a,b) for (i=a;i
            
             b;i--) #define Dec2(i,a,b) for (i=a;i>=b;i--) #define Sca_d(x) scanf("%d",&x) #define Sca_s(x) scanf("%s",x) #define Sca_c(x) scanf("%c",&x) #define Sca_f(x) scanf("%f",&x) #define Sca_lf(x) scanf("%lf",&x) #define Fill(x,a) memset(x,a,sizeof(x)) template 
             
               T gcd(T a,T b) { return b==0?a:gcd(b,a%b); } template 
              





                T lcm(T a,T b) { return a/gcd(a,b)*b; } const int MAXN=110; int N,M; struct Node { int number,p; }; Node node[MAXN]; int dp[MAXN][MAXN];//dp[i][j]代表第i点用j个士兵所能够取得的最大值 int adj[MAXN][MAXN]; //adj[k][0]存储的是第k个点是多少个点的父亲 //其子节点编号为adj[k][1]..adj[k][k] int vis[MAXN]; //vis[k]表示在搜索过程中，第k个点是否走过 void dfs(int root) { int i,j,k; vis[root]=1; int num=(node[root].number+19)/20; For2(i,num,M) dp[root][i]=node[root].p; For2(i,1,adj[root][0])//adj[k][0]存储的是第k个点是多少个点的父亲 //其子节点编号为adj[k][1]..adj[k][k] { int u=adj[root][i]; if (vis[u]) continue;//如果之前已经访问过u结点，则当前的root为u的子节点，则不需再次访问u dfs(u);//遍历子节点 Dec2(j,M,num) For2(k,1,M-j) if (dp[u][k]) dp[root][j+k]=max(dp[root][j+k],dp[root][j]+dp[u][k]); } } int main() { //input; int b,e,i,j,k; while(cin>>N>>M) { if (N==-1&&M==-1) break; Fill(vis,0); Fill(dp,0); Fill(adj,0); For2(i,1,N) Sca_d(node[i].number),Sca_d(node[i].p); For1(i,1,N) { Sca_d(b); Sca_d(e); adj[b][++adj[b][0]]=e; adj[e][++adj[e][0]]=b; } if (M==0) printf("0\n"); else { dfs(1); printf("%d\n",dp[1][M]); } } return 0; }