题目:
题意:
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; }
---------------------------------------------------------------------------------
我还没有理解依赖背包问题的解法和思路,看了别人的还是不能够领悟,真是菜菜菜啊~~~~~~代码来自点击打开链接
-----------------------------------------------------------------------------------------------------
战斗,永不停歇。。。。。。。。我对今天的态度就是对我一生的态度。。。。。