hdu_1011(Starship Troopers) 树形dp

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1011

题意:打洞洞收集脑子，你带领一个军队，洞洞互联成一棵树，每个洞中有一些bug，要全部杀死这些虫子才可以取得这个洞中的脑子，只有杀死当前节点的bug才可以继续走下去，且如果有0个bug你仍要派遣一个士兵在这里，只不过可以士兵不停留。

题解：很清晰明了的树形dp了，但是某些人说过写题解就要写细致。。。所以我们还是来详细讲解一下树形dp吧。。。

树形dp：

这是一个很裸的树形dp，和一般的dp不同的是，树形dp有了分支，所以要考虑子孩子和父亲孩子之间的关系。及父亲的最大值来源于其自孩子反馈给他的结果。

我们考虑dp[i][j]表示当前以第i个节点为编号的已经考虑的子树种耗费j个士兵的情况可以获得的最大收益

（分析的时候自顶向下，实现自底向上，这也是dfs的思想，树形dp一般都是在dfs过程中实现的）

考虑如果我们知道了当前节点所有子孩子的dp值，即我们知道了给当前已经考虑的孩子分着多少个士兵可以获得他和子孩子的最大收益，那么再考虑他的下一个子孩子的时候

就可以在此基础上枚举将士兵挨个分给新的子孩子的时候的最大收益，最后我们考虑完所有的子孩子，并把所有士兵都分下去就是结果了。

给出dp方程： dp[i][j] = max(dp[i][j],dp[i][j-k]+dp[son][k]);

画个图来帮助理解一下：

是不是很简单腻~图上没有说一些细节，和一般的dp一样，要考虑之前计算的点是否会被覆盖问题，在枚举j时候要从m向前搜索，因为如果从后往前，计算后面dp[i][j]的时候用到dp[i][j-k]已经被修改过了。还有一个细节就是如何保证当前节点有没有bug都分给一个士兵，这个很简单，只要k从1开始循环就可以了，即保证了无论怎样都给这个节点一个士兵。

代码：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N = ;

 int n,m;

 int cost[N],value[N];

 int vis[N];

 struct Edge{

     int to;

     int next;

 }edge[N*N];

 int Ecnt;

 int head[N];

 int dp[N][N];

 void init()

 {

     for(int i = ; i <= n; i++ ){

         head[i] = -;

         vis[i] = ;

     }

     Ecnt = ;

     memset(dp,,sizeof(dp));

 }

 void add(int from, int to)

 {

     edge[Ecnt].to = to;

     edge[Ecnt].next = head[from];

     head[from] = Ecnt++;

     edge[Ecnt].to = from;

     edge[Ecnt].next = head[to];

     head[to] = Ecnt++;

 }

 void dfs(int id)

 {

     vis[id] = ;

     int tm;

     if(m<cost[id]) return;

     for(int j = cost[id]; j <= m; j++) dp[id][j] = value[id];

     for(int d = head[id]; d!=-; d = edge[d].next)

     {

         tm = edge[d].to;

         if(!vis[tm]){

             dfs(tm);

             for(int j = m; j >= cost[id]; j--){

                 for(int k = ; k <= (j-cost[id]); k++){

                     if(j-k>=cost[id])

                     dp[id][j] = max(dp[id][j],dp[id][j-k]+dp[tm][k]);

                 }

             }

         }

     }

     return;

 }

 int main()

 {

     int tm,tm1,tm2;

     while(~scanf("%d%d",&n,&m))

     {

         if(n==-&&m==-) return ;

         for(int i = ; i <= n; i++)

         {

             scanf("%d %d",&tm,&value[i]);

             cost[i] = (tm+)/;

         }

         init();

         for(int i = ; i < n; i++)

         {

             scanf("%d %d",&tm1,&tm2);

             add(tm1,tm2);

         }

         vis[] = ;

         if(m==){printf("0\n");continue;}

         dfs();

         printf("%d\n",dp[][m]);

     }

     return ;

 }

巴特西

hdu_1011(Starship Troopers) 树形dp

最新文章

热门文章