# 42 条题解

• @ 2017-05-28 13:35:07
``````#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

struct p_s_1
{
int v;
vector<int> s;
};

int n,m;
vector<vector<int> > f;
vector<p_s_1> a;

void work_1(int now)
{
vector<int> v;
v.resize(m+1,0);
for (int i=1;i<a[now].s.size();i++)
{
work_1(a[now].s[i]);
for (int j=m;j>0;j--)
for (int k=j;k>0;k--)
v[j]=max(v[j],v[j-k]+f[a[now].s[i]][k]);
}
for (int i=m;i>0;i--)
f[now][i]=max(f[now][i],v[i-1]+a[now].v);
}

int main()
{
while (~scanf("%d%d",&n,&m))
{
a.resize(n+1);
for (int i=1;i<=n;i++)
{
int s_n;
scanf("%d%d",&a[i].v,&s_n);
a[i].s.resize(s_n+1,0);
for (int j=1;j<=s_n;j++)
scanf("%d",&a[i].s[j]);
}
f.resize(n+1);
for (int i=1;i<=n;i++)
f[i].resize(m+1,0);
work_1(1);
printf("%d\n",f[1][m]);
}
}
``````
• @ 2017-05-28 13:35:33

很H2O的题

• @ 2016-11-10 23:48:44

vijos的评测机就是快...暴力都能过
第一个点输出0不是负数

• @ 2016-08-20 10:44:52

多叉转成二叉，哪里错了？
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define N 1010
#define INF 1000000001
using namespace std;
int n,m;
int v[N];
struct data
{
int l,r;
}a[N];
{
int p=a[w].l;
if(a[w].l==0)a[w].l=c;
else
{
while(a[p].r!=0)
p=a[p].r;
a[p].r=c;
}
}
int f[1001][1001];
void dfs(int w,int num)
{
int p;
if(w==0||num==0)
{
f[w][num]=0;
return;
}
if(f[w][num]!=-1)
return;
dfs(a[w].r,num);
f[w][num]=f[a[w].r][num];
for(int k=0;k<num;k++)
{
dfs(a[w].l,k);
dfs(a[w].r,num-k-1);
f[w][num]=max(f[w][num],f[a[w].l][k]+f[a[w].r][num-1-k]+v[w]);
}
}
int main()
{
//freopen("D://in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
f[i][j]=-1;
}
for(int i=1;i<=n;i++)
{
int s;
scanf("%d%d",&v[i],&s);
for(int j=1;j<=s;j++)
{
int t;
scanf("%d",&t);
}
}
dfs(1,m);
cout<<f[1][m];
return 0;
}

• @ 2014-08-18 17:54:21

评测结果
编译成功

Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
63 lines compiled, 0.1 sec , 28400 bytes code, 1628 bytes data

测试数据 #0: Accepted, time = 0 ms, mem = 8596 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 8600 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 8596 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 8596 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 8596 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 8596 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 8596 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 8600 KiB, score = 10

测试数据 #8: Accepted, time = 46 ms, mem = 8608 KiB, score = 10

测试数据 #9: Accepted, time = 31 ms, mem = 8596 KiB, score = 10

Accepted, time = 137 ms, mem = 8608 KiB, score = 100

代码
var
n,m,t:longint;
a,list,count:array[0..1000]of longint;
f,table:array[0..1000,0..1000]of longint;
procedure dfs(x:longint);
var
i:longint;
begin
t:=t+1;
list[t]:=x;
for i:=1 to table[x,0]do
begin
dfs(table[x,i]);
count[x]:=count[x]+count[table[x,i]];
end;
count[x]:=count[x]+1;
end;
procedure int;
var
i,j,k,s:longint;
begin
fillchar(table,sizeof(table),0);

for i:=1 to n do
begin
table[i,0]:=s;
for j:=1 to s do
begin
table[i,j]:=k;
end;
end;
t:=0;
dfs(1);
end;
function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end;
procedure doing(v,x:longint);
var
i,j:longint;
begin
for i:=1 to n do
begin
f[i,0]:=0;
f[i,1]:=a[list[i]];
end;
for i:=n downto 1 do
for j:=1 to m do
f[i,j]:=max(f[i+1,j-1]+a[list[i]],f[i+count[list[i]],j]);

end;
begin
int;
doing(1,m);
write(f[1,m]);
end.

• @ 2014-08-18 17:39:25

测试数据 #0: Accepted, time = 0 ms, mem = 196440 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 196440 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 196440 KiB, score = 10

测试数据 #3: Accepted, time = 7 ms, mem = 196444 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 196444 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 196444 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 196440 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 196444 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 196444 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 196444 KiB, score = 10

Accepted, time = 82 ms, mem = 196444 KiB, score = 100

• @ 2014-08-18 17:38:50

var
list,count,a:array[0..5000] of longint;

table,opt:array[0..5000,0..5000] of longint;

c,w,m,s,t,i,j,top,sum,n,k:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a);
exit(b);
end;

function dfs(k:longint):longint;
var
i:longint;
begin
top:=top+1;
list[top]:=k;
for i:=1 to table[k,0] do
count[k]:=count[k]+dfs(table[k,i]);
count[k]:=count[k]+1;
exit(count[k]);
end;

procedure dp(v,x:longint);
var i,j:longint;
begin
for i:=1 to n do
begin
opt[i,0]:=0;
opt[i,1]:=a[list[i]];
end;

for i:=n downto 1 do
for j:=1 to m do
opt[i,j]:=max(opt[i+1,j-1]+a[list[i]],opt[i+count[list[i]],j])
end;
begin

for i:=1 to n do
begin
table[i,0]:=s;

for j:=1 to s do
begin
table[i,j]:=w;
end;

end;
dp(1,m);
writeln(opt[1,m]);
end.
请勿直接粘贴 我删除了几句 主要看算法

• @ 2014-08-18 17:34:31

var
f:array[0..1001,0..1001]of longint;
count,list,left,right,p:array[0..1001]of longint;
sum,top,t,s,j,n,m,i:longint;
function max(a,b:longint):longint;
begin
if a>b then
exit(a)
else
exit(b);
end;
function dfs(k:integer):longint;
var
t:integer;
begin
t:=0;
top:=top+1;
list[top]:=k;
count[k]:=1;
if left[k]>0 then
count[k]:=dfs(left[k])+1;
if right[k]>0 then
t:=dfs(right[k]);
exit(count[k]+t);
end;
begin

for i:=1 to n do
begin
for j:=1 to s do
begin
right[t]:=left[i];
left[i]:=t;
end;
end;
dfs(1);
for i:=1 to n do
begin
f[i,0]:=0;
f[i,1]:=p[list[i]];
end;
for i:=n-1 downto 0 do
for j:=1 to m do
f[i,j]:=max(f[i+1,j-1]+p[list[i]],f[i+count[list[i]],j]);
for i:=1 to m do
sum:=max(sum,f[1,i]);
writeln(sum);
end.

• @ 2009-11-08 21:38:15

第一个数据点竟然是负的!!!XD

WA　Ｎ次后writeln('0')解决!!

o(nm)算法请看WC2005何森论文中的算法三

• @ 2009-10-29 08:29:29

orz orz orz orz

orz orz orz orz

noi2009徐持衡论文~~

• @ 2009-10-27 19:08:27

怨念啊。。

记录下个子树的数组调用时下表写错了，浪费昨天一晚上时间，6次提交

话说先序遍历的时候，在所有儿子调用完之后先序遍历的指针就刚好指向下一个子树的位置，直接记录就行了-.-

• @ 2009-10-25 12:43:44

边界是 f[n,i]:=max(0,p[a[n]])! 不是 f[n,i]:=max(0,p[n]);

要不然就一直90了.当然对于这道题,n+1的边界可以不写,正好是0.

程序还不到40行...很好写

• @ 2009-10-22 21:28:02

终于AC了，提示一下，m可以不选

• @ 2009-10-14 22:01:57

program v1642;

var

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

father,p,s,c,a:array[1..1000]of longint;

i,j,k,n,m:longint;

procedure work(r:longint);

var

i,j:longint;

begin

inc(k);

a[k]:=r;

for i:=1 to s[r] do

work(child[r,i]);

for i:=1 to s[r] do

c[r]:=c[r]+c[child[r,i]];

c[r]:=c[r]+s[r];

end;

begin

k:=0;

fillchar(a,sizeof(a),0);

for i:=1 to n do

begin

for j:=1 to s[i] do

begin

father[child]:=i;

end;

end;

k:=0;

work(1);

for i:=n downto 1 do

begin

for k:=1 to m do

begin

if f+p[a[i]]>f[i+c[a[i]]+1,k] then

f:=f+p[a[i]]

else f:=f[i+c[a[i]]+1,k];

end;

end;

writeln(f[1,m]);

end.

TMD奇怪

WA了N次，后来把边界判断删了就A了

• @ 2009-09-19 20:29:00

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

不在树形上的树形动规

感谢 chenxiaomi 的网址！ N*M 秒杀

• @ 2009-09-19 18:00:09

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

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

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

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

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

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

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

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

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

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

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

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

pay attention to 边界！！！！！！！！！！！！！！！

• @ 2009-09-15 10:10:42
• @ 2009-10-06 10:50:20

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

国家队论文实在太伟大了！O(NM)的算法实在太伟大了！

传统的树形DP只能超时....（注意班长一定要取！）

也感谢各位大牛的指教~

• @ 2009-09-12 14:55:28

大牛们发个pascal码好吗？谢谢了。

• @ 2009-09-06 20:48:27

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

using namespace std;

const int maxn = 1010, maxm = 10010;

const int oo = 1000000000;

struct Tnode

{

int son, next;

}tn[maxn];

int n, m;

int p[maxn];

int val[maxn];

int son_count[maxn];

int cur = 0;

int f[maxn][maxm];

void insert(int root, int son)

{

cur++;

tn[cur].son = son;

tn[cur].next = p[root];

p[root] = cur;

}

void get_sonCount(int root)

{

int next = p[root];

while(next != 0)

{

get_sonCount(tn[next].son);

son_count[root] += son_count[tn[next].son];

next = tn[next].next;

}

son_count[root]++;

}

void dfs(int root)

{

f[root][0] = 0;

f[root][1] = val[root];

int next = p[root];

int haved = 1;

while(next != 0)

{

int son = tn[next].son;

dfs(son);

int tmp = min(haved,m);

haved += son_count[son];

for(int i = min(haved,m); i > 1; i--)

{

for(int j = min(i-1, son_count[son]); j >= 1; j--)

{

if(i-j>tmp) break;

f[root][i] >?= f[root] + f[son][j];

}

}

next = tn[next].next;

}

}

int main()

{

cin>>n>>m;

for(int i = 1; i >val[i];

int tmp;

cin>>tmp;

while(tmp > 0)

{

tmp--;

int son;

cin>>son;

insert(i, son);

}

}

get_sonCount(1);

for(int i = 1; i

• @ 2009-10-26 09:59:38

谁给一下O(NM)算法的论文

ID
1642

8

1797

253

14%

1