典型的树形动态规划。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 阅读(694)
评论(1) 编辑 收藏 引用 所属分类:
题目分类：动态规划