hdu 1561【树形dp+01背包】

http://acm.hdu.edu.cn/showproblem.php?pid=1561

    很容易想到如果是要攻克v城需要先攻克u城的话，可以建u到v的边。但是如果能够直接攻克u城呢？无边可建，这样就无法形成一棵树。因此虚拟出一个0结点去连接可直接攻克的城。这样只需多打一次0城即可。定义状态dp[i][j]表示当前结点为i时，选取j个节点（j为i的子节点或i）能获得的最大价值。

dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v[u][i]][k])表示：
在u号点的第i个子节点中选k个点加上在u号点选j-k个子节点与直接在u号点选j个子节点那个更优。

显然dp[i][1]=val[1]，剩下的就是01背包了，感觉还是不太熟。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=225;
vector<int> v[maxn];
int dp[maxn][maxn];
int N,M,x;
int val[maxn];

void dfs(int u,int m)
{
    dp[u][1]=val[u];
    int len=v[u].size();
    for(int i=0;i<len;i++){
        if(m>1) dfs(v[u][i],m-1);
        for(int j=m;j>1;j--)//由于0节点必选，所以j>1就行了
            for(int k=1;k<j;k++)
            dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v[u][i]][k]);
    }
}

int main()
{
    while(cin>>N>>M&&!(N==0&&M==0))
    {
        memset(dp,0,sizeof(dp));
        memset(val,0,sizeof(val));
        for(int i=0;i<=N;i++) v[i].clear();
        for(int i=1;i<=N;i++){
            cin>>x>>val[i];
            v[x].push_back(i);
        }
        dfs(0,M+1);
        cout<<dp[0][M+1]<<endl;
    }
    return 0;
}