hdu1011 和 hdu1561类似,给定每个节点的花费以及价值,并且子节点必须在父亲节点取到以后才可以被取到
相当于是在树上进行的01背包
dp时考虑每一个子树 root和它的每一个儿子,状态转移方程为
dp[root][j]=max(dp[root][j],dp[root][j-k]+dp[ son[p] ][ k ])
以下为ac代码
hdu1011:这题有一个小坑,最后必须要剩余至少一个人。。开始没考虑到,一直wa
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<queue>
#define mod 1000000007
#define MAX 100000000
using namespace std;
int t,n,m,p,k,tt;
int map[][];
int dp[][];
int a[];
int w[];
int vi[];
void dfs(int s)
{
vi[s]=;
int cost=(w[s]+)/;
for(int i=cost;i<=m;i++)
dp[s][i]=a[s];
for(int i=;i<=n;i++)
{
if(!map[s][i])
continue;
if(vi[i])
continue;
dfs(i);
for(int k=m;k>=cost;k--)
for(int j=;j+cost<=k;j++)
dp[s][k]=max(dp[s][k],dp[s][k-j]+dp[i][j]); }
}
int main()
{
while(scanf("%d%d",&n,&m)&&(n!=-||m!=-))
{
int x,y;
memset(map,,sizeof(map));
memset(dp,,sizeof(dp));
memset(vi,,sizeof(vi));
a[]=;
for(int i=;i<=n;i++)
{
scanf("%d%d",w+i,a+i);
}
for(int i=;i<n;i++)
{
scanf("%d%d",&x,&y);
map[x][y]=;
map[y][x]=;
}
if(m==)
{
puts("");
continue;
}
dfs();
printf("%d\n",dp[][m]);
}
return ;
}
hdu 1561
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<queue>
#define mod 1000000007
#define MAX 100000000
using namespace std;
int t,n,m,p,k,tt;
int map[][];
int dp[][];
int a[];
void dfs(int s)
{
for(int j=;j<=m+;j++)
dp[s][j]=a[s];
for(int i=;i<=n;i++)
{
if(!map[s][i])
continue;
dfs(i);
for(int k=m+;k>=;k--)
for(int j=;j+<=k;j++)
dp[s][k]=max(dp[s][k],dp[s][k-j]+dp[i][j]); }}
int main()
{
while(scanf("%d%d",&n,&m)&&(n+m))
{
memset(map,,sizeof(map));
memset(dp,,sizeof(dp));
int x;
a[]=;
for(int i=;i<=n;i++)
{
scanf("%d",&x);
map[x][i]=;
scanf("%d",a+i);
}
dfs();
printf("%d\n",dp[][m+]);
}
return ;
}