题解 - Vijos

1

Sky1231 (sky1231) LV 10 @ 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]);
    }
}

sky1231 @ 2017-05-28 13:35:33

很H2O的题

0

raffica LV 10 @ 2016-11-10 23:48:44

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

0

1263659722 LV 10 @ 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];
void add(int w,int c)
{
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);
add(i,t);
}
}
dfs(1,m);
cout<<f[1][m];
return 0;
}

0

dllp LV 9 @ 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
Linking foo.exe
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);

read(n,m);
for i:=1 to n do
begin
read(a[i],s);
table[i,0]:=s;
for j:=1 to s do
begin
read(k);
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.

0

1031389972 LV 8 @ 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

0

1031389972 LV 8 @ 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

read(n,m);
for i:=1 to n do
begin
read(a[i],s);
table[i,0]:=s;

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

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

0

Sanmee360 LV 8 @ 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

read(n,m);
for i:=1 to n do
begin
read(p[i],s);
for j:=1 to s do
begin
read(t);
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.

0

3334 LV 7 @ 2009-11-08 21:38:15

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

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

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

0

db_db_Jacky LV 10 @ 2009-10-29 08:29:29

orz orz orz orz

orz orz orz orz

noi2009徐持衡论文~~

0

332404521 LV 9 @ 2009-10-27 19:08:27

怨念啊。。

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

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

0

ASCE LV 8 @ 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行...很好写

0

mauricejoe LV 8 @ 2009-10-22 21:28:02

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

0

招财猪 LV 8 @ 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;

read(n,m);

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

for i:=1 to n do

begin

read(p[i],s[i]);

for j:=1 to s[i] do

begin

read(child);

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了

0

陈亮宇 LV 10 @ 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 秒杀

0

jacklv LV 10 @ 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 边界！！！！！！！！！！！！！！！

0

chenxiaomi LV 8 @ 2009-09-15 10:10:42

http://www.oibh.org/bbs/thread-33048-1-1.html

O(nm)算法

0

zhh1993 LV 10 @ 2009-10-06 10:50:20

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

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

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

也感谢各位大牛的指教~

0

king465659 LV 8 @ 2009-09-12 14:55:28

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

0

lianggj2 LV 8 @ 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

0

飞翔 LV 10 @ 2009-10-26 09:59:38

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

题解

42 条题解

班长的任务

信息

状态

开发

支持

题解

42 条题解

班长的任务

信息

状态

开发

支持

还没有账户？

登录