HDU 1011 Starship Troopers---树形dp+有依赖的背包

dp[i][j]表示 用i 个士兵 在j为根节点的 最大值

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;

struct node{
	int a,b;
}p[110];
vector<int> q[110];   //用vector存 邻接表
int dp[110][110],f[110],m;
void dfs(int s,int k)
{
	int i,j,t;
	f[k]=1;
	for(i=p[k].a;i<=m;i++) //赋初值，比较神奇。。
		dp[i][k]=p[k].b;
	int len=q[k].size();
	for(i=0;i<len;i++)  //一个分组背包
	{
		if(f[q[k][i]]==1)
			continue;
		if(s > p[k].a)
		dfs(s-p[k].a,q[k][i]);
		for(j=s;j-p[k].a>=0;j--)// 这里注意要 j-p[k].a
			for(t=1;t<=j-p[k].a;t++)
				dp[j][k]=max(dp[j][k],dp[j-t][k]+dp[t][q[k][i]]);
	}
}
int main()
{
	int n,i,k;
	while(scanf("%d%d",&n,&m),n!=-1||m!=-1){
		int t1,t2;
		memset(dp,sizeof(dp));
		memset(f,sizeof(f));
		for(i=1;i<=n;i++){
			q[i].clear();
			scanf("%d%d",&t1,&t2);
			p[i].a=(t1%20==0)?(t1/20):(t1/20+1);//...
			p[i].b=t2;
		}
		for(i=1;i<n;i++)
		{
			scanf("%d%d",&t2);
			q[t1].push_back(t2);
			q[t2].push_back(t1);
		}
		if(m==0)     //这条件不加，就错了！
			printf("0n");
		else
		{
		dfs(m,1);
		printf("%dn",dp[m][1]);
		}
	}
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!