典型的樹(shù)形動(dòng)態(tài)規(guī)劃。DP之前需要用左兒子右兄弟的方法構(gòu)造樹(shù)。定義d[i][j]表示在以第i個(gè)結(jié)點(diǎn)為根的樹(shù)上選擇j個(gè)結(jié)點(diǎn)獲得的最大分?jǐn)?shù)。

d[i][j]=max(d[right[i]][j]，d[left[i]][k]+d[right[i]][j-k-1])；0<=k<=j-1

以上狀態(tài)轉(zhuǎn)移方程解釋為：

1、 不選擇根節(jié)點(diǎn)，j個(gè)結(jié)點(diǎn)全部在右子樹(shù)上選擇；

2、 選擇根節(jié)點(diǎn)，從左子樹(shù)上選擇k個(gè)，右子樹(shù)上選擇j-k-1個(gè)，0<=k<=j-1。

邊界條件為：

d[nil][i]=0；nil=n+1，0<=i<=m。C語(yǔ)言中下標(biāo)不能從-1開(kāi)始，所以把nil的值設(shè)為n+1，因?yàn)?/span>n+1這個(gè)結(jié)點(diǎn)是不存在的。

d[i][0]=0；0<=i<=n+1

以下是我的代碼：

#include<stdio.h>
#define MAXN 302
typedef struct
{
    long left,right;
}Tree;
long n,m,nil,ans,s[MAXN]={0},d[MAXN][MAXN];
Tree tree[MAXN];
long max(long a,long b)
{
    return (a>b?a:b);
}
void ins(long father,long son)
{
    long p;
    if(tree[father].left==nil)
      tree[father].left=son;
    else
    {
       p=tree[father].left;
       while(tree[p].right!=nil)
         p=tree[p].right;
       tree[p].right=son;
    }
}
void init()
{
    long i,j,t;
    scanf("%ld%ld",&n,&m);
    nil=n+1;
    for(i=0;i<=n;i++)
    {
       tree[i].left=nil;
       tree[i].right=nil;
    }// Clear
    for(i=1;i<=n;i++)
    {
       scanf("%ld%ld",&t,&s[i]);
       ins(t,i);
    }
    for(i=0;i<=nil;i++)
      for(j=0;j<=m;j++)
      {
         if(i==nil||j==0) d[i][j]=0;
         else d[i][j]=-1;
      }
    
}
long dp(long node,long sum)
{
    long i;
    if(d[node][sum]>=0)
      return d[node][sum];
    // 已經(jīng)計(jì)算過(guò) 
    d[node][sum]=dp(tree[node].right,sum);
    for(i=0;i<=sum-1;i++)
      d[node][sum]=max(d[node][sum],dp(tree[node].left,i)+dp(tree[node].right,sum-i-1)+s[node]);
    return d[node][sum];
}
int main()
{
    freopen("score.in","r",stdin);
    freopen("score.out","w",stdout);
    init();
    ans=dp(tree[0].left,m);
    printf("%ld\n",ans);
return 0;
}