典型的樹形動態規劃。DP之前需要用左兒子右兄弟的方法構造樹。定義d[i][j]表示在以第i個結點為根的樹上選擇j個結點獲得的最大分數。
d[i][j]=max(d[right[i]][j]，d[left[i]][k]+d[right[i]][j-k-1])；0<=k<=j-1
以上狀態轉移方程解釋為：
1、 不選擇根節點，j個結點全部在右子樹上選擇；
2、 選擇根節點，從左子樹上選擇k個，右子樹上選擇j-k-1個，0<=k<=j-1。
邊界條件為：
d[nil][i]=0；nil=n+1，0<=i<=m。C語言中下標不能從-1開始，所以把nil的值設為n+1，因為n+1這個結點是不存在的。
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];
// 已經計算過
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;
}
posted on 2010-01-06 20:00
lee1r 閱讀(737)
評論(1) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃