HDOJ 1561 - 树形DP,泛化背包

刚看题...觉得这不是棵树...可能有回路...仔细一想..这还真是棵树(森林)...这是由于每个城堡所需要提前击破的城堡至多一个..对于一个城堡.其所需提前击破的城堡作为其父亲构图....

dp[k][i]代表以k为跟的子树击破i个城堡所能获得的最大收益...泛化背包问题...

Program:

#include<iostream>

#include<stack>

#include<queue>

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<cmath>

#define ll long long

#define oo 1000000007

#define MAXN 205

using namespace std;

vector<int> Tree[MAXN];

int n,m,v[MAXN],ans[MAXN],dp[MAXN][MAXN];

bool root[MAXN];

void dfs(int x,int t)

{

      int i,j,k,num;

      if (t>m) return;

      dp[x][1]=v[x];

      num=Tree[x].size();

      for (i=0;i<num;i++)

      {

            dfs(Tree[x][i],t+1);

            for (j=m;j>=1;j--)

               for (k=1;k<=m-j;k++)

                  dp[x][j+k]=max(dp[x][j+k],dp[x][j]+dp[Tree[x][i]][k]);

      }

      return;

}

int main()

{

      int i,j,k;

      while (~scanf("%d%d",&n,&m) && n && m)

      {

             for (i=1;i<=n;i++) Tree[i].clear();

             memset(root,true,sizeof(root));

             for (i=1;i<=n;i++)

             {

                   int x,c;

                   scanf("%d%d",&x,&c);

                   Tree[x].push_back(i);

                   v[i]=c;

                   if (x) root[i]=false;

             }

             memset(dp,0,sizeof(dp));

             memset(ans,0,sizeof(ans));

             for (i=1;i<=n;i++)

               if (root[i])

               {

                      dfs(i,1);

                      for (j=m;j>=0;j--)

                         for (k=0;k<=m-j;k++)

                             ans[j+k]=max(ans[j+k],ans[j]+dp[i][k]);

               }

            for (i=m;i>=0;i--)

              if (ans[i]) break;

            printf("%d\n",ans[i]);

      }

      return 0;

}