题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1561
题目大意：从树根开始取点。最多取m个点，问最大价值。
解题思路：
cost=1的树形背包。
有个虚根0，取这个虚根也要cost，所以最后的结果是dp[0][m+1]。
本题是cost=1的特殊背包问题，在两个for循环上有一个优化。
for(f+1...j....cost)
for(1....k...j-cost)
其中f为当前已经dfs子结点个数。之所以+1，是因为根要预留一个空间。
f+=dfs(t)，dfs(t)返回的是子点t的f+1。
其实可以直接把f+1写成m+1, 不过要多好多次没必要的循环。
#include "cstdio"
#include "vector"
#include "cstring"
using namespace std;
#define maxn 205
int n,m,u,dp[maxn][maxn],w[maxn],head[maxn],tol;
struct Edge
{
int to,next;
}e[maxn];
void addedge(int u,int v)
{
e[tol].to=v;
e[tol].next=head[u];
head[u]=tol++;
}
int dfs(int root)
{
int i=root,cost=,f=;
for(int i=cost;i<=m;i++) dp[root][i]=w[root];
if(head[root]==-) return ;
for(int a=head[root];a!=-;a=e[a].next)
{
int t=e[a].to;
f+=dfs(t);
for(int j=f+;j>=;j--)
{
for(int k=;k<=j-cost;k++)
{
dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[t][k]);
}
}
}
return f+;
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d%d",&n,&m)&&n&&m)
{
memset(head,-,sizeof(head));
tol=;
for(int i=;i<=n;i++)
{
scanf("%d%d",&u,&w[i]);
addedge(u,i);
}
dfs();
printf("%d\n",dp[][m+]);
memset(dp,,sizeof(dp));
}
}
| 11910646 | 2014-10-19 14:01:53 | Accepted | 1561 | 0MS | 400K | 1099 B | C++ | Physcal |