HDU1561 The more, The Better（树形依赖背包）

题目链接
题意：略
解法：09《浅谈几类背包问题》有详解

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>
using namespace std;
const int maxn=205;
#define LL long long
#define pb push_back
#define cl(a,b) memset(a,b,sizeof(a))

LL val[maxn];
LL dp[maxn][maxn];
int n,m;
int x[maxn];
void dfs(int k,int C){
    if(C<=0)return ;
    for(int i=1;i<=n;i++)if(x[i]==k){
        for(int j=0;j<C;j++)
            dp[i][j]=dp[k][j]+val[i];
        dfs(i,C-1);
        for(int j=1;j<=C;j++){
            dp[k][j]=max(dp[k][j],dp[i][j-1]);
        }
    }
}
int main(){
    while(~scanf("%d%d",&n,&m)&&(n||m)){
        for(int i=1;i<=n;i++){
            scanf("%d%lld",&x[i],&val[i]);
        }
        cl(dp,0);
        dfs(0,m);
        printf("%lldn",dp[0][m]);
    }
    return 0;
}