HDU 1011(星河战队 树形DP)

题意是说在一个洞穴中有许多房间,每个房间中有一些虫子和大脑,这些房间之间用隧道相连形成一棵树,士兵们杀虫子的能力有限,也可以直接杀死虫子而不消耗士兵战斗力,但这样就无法得到房间中的大脑,士兵们不能走回头路,问给定士兵数量时能得到的大脑最大值。

在树上进行动态规划,对于每个节点来说,选择了它,就要损失士兵战斗力,不选择它,就可以将这些省下来的士兵战斗力用在后面的房间中,后面的房间将最优选择传递到当前位置,以此来判断从而得到最优解。
转移方程:dp[ i ][ j ] = max(dp[ i ][ j ], dp[ i ][ j-k ]+dp[ son(i) ][ k ])

dp[ i ][ j ] 表示以节点 i 为根节点时消耗 j 个士兵所能得到的最大大脑数。

开始的时候直接将每个士兵按战斗力分成每个战斗力为 1 的士兵,也就是说将士兵数量乘以 20 ,企图直接可以用士兵数和虫子数进行加减运算,但是这样很明显是错误的,因为如果一个房间中的虫子数模 20 不为零,也就是说并不能完全发挥一个士兵的战斗力时,要取到这个房间的大脑,就需要再消耗一个士兵,即士兵战斗力并不等于士兵手中的子弹数(这样说好像更复杂了,意思就是每个士兵不一定会杀满 20 只虫子)。

还有一点就是士兵数是可以为零的,但是必须要有人进去才能得到大脑,无论里面是否有虫子。

代码如下:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN = 110;
 4 int N,M;
 5 struct Node
 6 {
 7     int enemy,aim;
 8 }node[MAXN];//存储所有节点上的信息
 9 int dp[MAXN][MAXN];//dp[i][j]表示根节点为 i 时,用掉 j 个士兵获得的最大值
10 int mp[MAXN][MAXN];//存图,mp[i][0]表示与节点 i 相连的边的数目
11 bool vis[MAXN];//记录节点的访问情况
12 void dfs(int root)
13 {
14     vis[root] = true;
15     int num = (node[root].enemy+19)/20;//获得当前节点需要的士兵数目
16     for(int i = num; i <= M; i++)  dp[root][i] = node[root].aim;
17     for(int i = 1; i <= mp[root][0]; i++)//开始遍历与根节点相连的子节点
18     {
19         int u = mp[root][i];
20         if(vis[u]) continue;
21         dfs(u);
22         for(int j = M; j >= num; j--)
23             for(int k = 1; j+k <= M; k++)
24                 if(dp[u][k])//判断是否应该取当前节点 u 
25                   dp[root][j+k] = max(dp[root][j+k],dp[root][j]+dp[u][k]);
26     }
27 }
28 int main()
29 {
30     int a,b;
31     while(scanf("%d%d",&N,&M))
32     {
33         if(N == -1 && M == -1) break;
34         memset(vis,0,sizeof(vis));
35         memset(dp,0,sizeof(dp));
36         memset(mp,0,sizeof(mp));
37         for(int i = 1; i <= N; i++)
38             scanf("%d%d",&node[i].enemy,&node[i].aim);
39         for(int i = 1; i < N; i++)
40         {
41              scanf("%d%d",&a,&b);
42              mp[a][0]++;
43              mp[b][0]++;
44              mp[a][mp[a][0]] = b;
45              mp[b][mp[b][0]] = a;
46         }
47         if(M==0) puts("0");//有可能己方没有士兵,但要求至少要有人进去
48         else
49         {
50             dfs(1);
51             printf("%d
",dp[1][M]);
52         }
53 
54     }
55     return 0;
56 }
View Code

这道题还是借鉴了很多大佬的博客才做出来的,感谢这些大佬的分享 ^_^

日后若能有更好的想法,再来完善。 希望看到的大神不吝赐教 orz
原文地址:https://www.cnblogs.com/Taskr212/p/9516466.html