hdu 1011 Starship Troopers (依赖背包 树形dp)

前端之家收集整理的这篇文章主要介绍了hdu 1011 Starship Troopers (依赖背包 树形dp)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

题目:

链接点击打开链接

题意:

n个房间组成一棵树,你有m个战队,从1号房间开始依次clear每个房间,在每个房间需要花费的战队个数是bugs/20,得到的价值是the possibility of capturing a brain,求最大的价值。

算法:

树形dp,有依赖的背包问题。(依次clear每个房间)

思路:

状态转移dp[i][j]表示根结点为i时(房间i)花费j个战队能够得到的最大价值(捕捉到一个brain最大的可能值)。递归求出每个根结点处的最大值,最后dp[1][m]就是答案。

代码

/*树型dp*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 110


struct Node
{
  int num;
  int p;
} node[MAXN];


int n,m;
int dp[MAXN][MAXN];//dp[i][j]表示根结点为i(房间i)时,用j个战队能够捕捉一个brain最大的可能值
int vis[MAXN];
int tree[MAXN][MAXN];//存树


void dfs(int root)
{
  int numm = (node[root].num+19)/20;
  vis[root] = 1;
  for(int i=numm; i<=m; i++)//初始化
    dp[root][i] = node[root].p;
  for(int i=1; i<=tree[root][0]; i++)
  {
    int u = tree[root][i];
    if(vis[u])
        dfs(u);
    for(int j=m; j>=numm; j--)//01背包处理(转化为物品组,按分组背包)
    {
      for(int k=1; k+j<=m; k++)
      {
        if(dp[u][k])
          dp[root][j+k] = max(dp[root][j+k],dp[root][j]+dp[u][k]);
      }
    }
  }
}


int main()
{
  //freopen("input.txt","r",stdin);
  int a,b;
  while(scanf("%d%d",&n,&m) != EOF && (n!=-1 || m!=-1))
  {
    memset(dp,sizeof(dp));
    memset(vis,sizeof(vis));
    memset(tree,sizeof(tree));
    for(int i=1; i<=n; i++)
      scanf("%d%d",&node[i].num,&node[i].p);
    for(int i=1; i<=n-1; i++)
    {
      scanf("%d%d",&a,&b);
      tree[a][0]++;
      tree[a][tree[a][0]] = b;
      tree[b][0]++;
      tree[b][tree[b][0]] = a;
    }
    if(m == 0)
      printf("0\n");
    else
    {
      dfs(1);
      printf("%d\n",dp[1][m]);
    }
  }
  return 0;
}

---------------------------------------------------------------------------------

我还没有理解依赖背包问题的解法和思路,看了别人的还是不能够领悟,真是菜菜菜啊~~~~~~代码来自点击打开链接

-----------------------------------------------------------------------------------------------------

战斗,永不停歇。。。。。。。。我对今天的态度就是对我一生的态度。。。。。

原文链接:https://www.f2er.com/javaschema/285546.html

猜你在找的设计模式相关文章