题目链接: 

题目大意：从树根开始取点。最多取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 205int 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=1,f=0;    for(int i=cost;i<=m;i++) dp[root][i]=w[root];    if(head[root]==-1) return 1;    for(int a=head[root];a!=-1;a=e[a].next)    {        int t=e[a].to;        f+=dfs(t);        for(int j=f+1;j>=1;j--)        {            for(int k=1;k<=j-cost;k++)            {                dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[t][k]);            }        }    }    return f+1;}int main(){    //freopen("in.txt","r",stdin);    while(scanf("%d%d",&n,&m)&&n&&m)    {        memset(head,-1,sizeof(head));        tol=0;        for(int i=1;i<=n;i++)        {            scanf("%d%d",&u,&w[i]);            addedge(u,i);        }        dfs(0);        printf("%d\n",dp[0][m+1]);        memset(dp,0,sizeof(dp));    }}

 

11910646

2014-10-19 14:01:53

Accepted

0MS

400K

C++