测试数据 #0: Accepted, time = 0 ms, mem = 716 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 716 KiB, score = 20
测试数据 #2: Accepted, time = 15 ms, mem = 720 KiB, score = 20
测试数据 #3: Accepted, time = 31 ms, mem = 720 KiB, score = 20
测试数据 #4: Accepted, time = 62 ms, mem = 720 KiB, score = 20
Accepted, time = 108 ms, mem = 720 KiB, score = 100
代码
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
int f[302][302],score[302],brother[302],child[302];
bool visited[302][302];
int n,k;
void dfs(int i,int j)
{
if (visited[i][j]) return ;
visited[i][j]=true;
if ((i==0)||(j==0)) return;
dfs(brother[i],j);
f[i][j]=f[brother[i]][j];
for (int k=0;k<j;k++)
{
dfs(brother[i],k);
dfs(child[i],j-k-1);
f[i][j]=max(f[i][j],f[brother[i]][k]+f[child[i]][j-k-1]+score[i]);
}
}
int main()
{
cin>>n>>k;
fill(score,score+302,-10000);
score[n+1]=0;
fill(brother,brother+n+1,0);
fill(child,child+n+1,0);
for (int i=0;i<=n+1;i++)
for (int j=0;j<=n+1;j++)
{
f[i][j]=0;
visited[i][j]=false;
}

int a,b;
for(int i=1;i<=n;i++)
{
cin>>a>>b;
if (a==0) a=n+1;
brother[i]=child[a];
child[a]=i;
score[i]=b;
}
for (int i=1;i<=n+1;i++)
f[i][0]=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (child[i]==0) f[i][j]=score[i];
dfs(n+1,k+1);
cout<<f[n+1][k+1];
}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,t;
int v[301],s[301],count[301];
int a[301][301],f[301][301];
int list[301];
int tree_traversal(int k)
{
list[++t]=k;
if(s[k]==0){return ++count[k];}
for(int i=1;i<=s[k];i++)
count[k]+=tree_traversal(a[k][i]);
return ++count[k];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d%d",&x,&v[i]);
if(x!=0)a[x][++s[x]]=i;
else a[0][++s[0]]=i;
}
tree_traversal(0);
for(int i=2;i<=n+1;i++){f[i][0]=0;f[i][1]=v[list[i]];}
for(int i=n+1;i>=1;i--)
for(int j=2;j<=m+1;j++)
f[i][j]=max(f[i+1][j-1]+v[list[i]],f[i+count[list[i]]][j]);
printf("%d\n",f[1][m+1]);
return 0;
}
hzwer.com

type dd=record l,r,data:longint; end;
var
n,m,i,a,b:longint;
t:array[0..601] of dd;
c:array[0..601] of longint;
f:array[0..601,0..601] of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;

function dp(k,q:longint):longint;
var i:longint;
begin
if f[k,q]<>0 then exit(f[k,q]);
if (q=0) or (k=0) then exit(0);
f[k,q]:=dp(t[k].r,q);
for i:=1 to q do
f[k,q]:=max(f[k,q],dp(t[k].l,i-1)+dp(t[k].r,q-i)+t[k].data);
exit(f[k,q]);
end;

begin
readln(n,m);
for i:=1 to n do
begin
readln(a,b);
t[i].data:=b;
if c[a]=0 then
t[a].l:=i
else t[c[a]].r:=i;
c[a]:=i;
end;
writeln(dp(t[0].l,m));
end.

输出方案 有规律吗？？？ 求规律！

其实这个题可以写背包。。就是金明的预算方案不限制附件个数和附件是否有附件。。然后OTLsunmeng94..

多叉转二叉比较好写，貌似时间也快点？

这个题还算慈眉善目，如果还让输出方案，估计这个题的通过率要下降不少

此题有两种思路:

1 直接在多叉树的结构上做

f表示以i 课程为父亲结点的子树上选j 门课程的最多学分

f:=max(f,f[k,w]+f+cost[i])

{k为i的一个儿子,0=

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

方法: Tree_DP + 多叉树转二叉树

var i,m,j,n:longint;

f:array[0..1000,0..1000]of longint;

fa:array[1..1000]of longint;

v:array[0..1000]of longint;

son:array[0..1000,0..1000]of longint;

function max(a,b:longint):longint;

begin

if a>b then exit(a);

exit(b);

end;

procedure dp(i:longint);

var k,p,q,z:longint;

begin

if son=0 then exit;

for k:=1 to son do

dp(son);

for z:=1 to son do

for p:=m+1 downto 2 do

for q:=0 to p-1 do

f:=max(f,f+f[son,q]);

end;

begin

readln(n,m);

for i:=1 to n do

begin

readln(fa[i],v[i]);

son[fa[i],0]:=son[fa[i],0]+1;

son[fa[i],son[fa[i],0]]:=i;

f:=v[i];

end;

dp(0);

writeln(f[0,m+1]);

end.

树形DP

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms