随笔-65  评论-6  文章-0  trackbacks-0
 1 //状态转移方程:    dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[son[i]][k])    
 2 //                    以第i个城市为起点,攻占j个城市的最大收益
 3 
 4 #include <iostream>
 5 #include <cstring>
 6 using namespace std;
 7 #define MaxSize 205
 8 
 9 int dp[MaxSize][MaxSize];
10 int value[MaxSize];
11 int mapmap[MaxSize][MaxSize];
12 bool vis[MaxSize];
13 int n,m;
14 
15 inline int max(int a,int b){
16     return a>b?a:b;
17 }
18 
19 void dfs(int root){
20     int i,j,k,u;
21     dp[root][1]=value[root];
22     for(i=1;i<=mapmap[root][0];i++){
23         u=mapmap[root][i];//root之后可以选择攻占的城市
24         dfs(u);
25         for(j=m+1;j>0;j--){
26             for(k=1;k+j<=m+1;k++){
27                 dp[root][j+k]=max(dp[root][j+k],dp[root][j]+dp[u][k]);
28             }
29         }
30     }
31 }
32 
33 int main(){
34     //freopen("in.txt","r",stdin);
35     int i;
36     while (scanf("%d%d",&n,&m),(n||m)){
37         for(i=0;i<=n;i++)
38             mapmap[i][0]=0;
39         value[0]=0;
40         for(i=1;i<=n;i++){
41             int a;
42             scanf("%d %d",&a,&value[i]);
43             mapmap[a][0]++;
44             mapmap[a][mapmap[a][0]]=i;
45         }
46         memset(dp,0,sizeof(dp));
47         //问题的关键在于将0作为第零个城堡,价值为零,这样就可以实现大一统!
48         dfs(0);
49         printf("%d\n",dp[0][m+1]);//加入了第零个城堡,则m+1
50     }
51     return 0;
52 }
posted on 2012-07-12 22:15 Leo.W 阅读(423) 评论(1)  编辑 收藏 引用

评论:
# re: hdu 1561(The more, The Better) 2012-07-23 10:58 | 77
for(j=m+1;j>0;j--)
为什么j 从大到小而不是从小到大?  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理