讨论 / 评测机火星了吗
cszqwe 2009-10-23 07:00:00
点我顶贴 收藏 删除
状态: Unaccepted

测评机: Xeost[5]

得分: 20分

提交日期: 2009-10-23 12:21:00

有效耗时: 344毫秒

测试结果1: 通过本测试点|有效耗时250ms

测试结果2: 通过本测试点|有效耗时94ms

测试结果3: 测试结果错误.错误结果为:11

4 38 46

正确结果应为:20

28 36 87

测试结果4: 测试结果错误.错误结果为:11

4 38 46

正确结果应为:37

46 268

测试结果5: 测试结果错误.错误结果为:11

4 38 46

正确结果应为:31

98 132

测试结果6: 测试结果错误.错误结果为:11

4 38 46

正确结果应为:63

78 482 573

测试结果7: 测试结果错误.错误结果为:11

4 38 46

正确结果应为:57

190 922

测试结果8: 测试结果错误.错误结果为:11

4 38 46

正确结果应为:48

29 460

测试结果9: 测试结果错误.错误结果为:11

4 38 46

正确结果应为:53

265 689

测试结果10: 测试结果错误.错误结果为:11

4 38 46

正确结果应为:61

29 237 525

提交代码: program da;

var a:array[1..1000,1..1000]of longint;

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

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

b,c:array[1..1000]of longint;

d:array[1..2000]of longint;

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

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

function dg(i:longint):longint;

var j,k,t,y:longint;

dx,dy:array[1..1000]of longint;

begin

if e[i]=0 then exit(1);

k:=e[i];

for j:=1 to k do

dx[j]:=dg(f[i,j]);

for j:=1 to k do

for p:=j+1 to k do

if dx[j]<dx[p] then

begin

t:=dx[j];

dx[j]:=dx[p];

dx[p]:=t;

end;

p:=0;

for j:=1 to k do begin dy[j]:=dx[j]+j;if dy[j]>p then p:=dy[j];

end;dg:=p;

end;

procedure js(i:longint);

var j:longint;

begin

for j:=1 to n do

if (a[i,j]=1) and (c[j]=0) then

begin

inc(e[i]);

f[i,e[i]]:=j;

b[j]:=i;

c[j]:=1;

js(j);

c[j]:=0;

end;

end;

begin

readln(n);

for i:=2 to n do

begin

read(o);

a[i,o]:=1;

a[o,i]:=1;

end;

o:=maxlongint;

for i:=1 to n do

begin

fillchar(e,sizeof(e),0);

fillchar(f,sizeof(f),0);

fillchar(b,sizeof(b),0);

fillchar(c,sizeof(c),0);

c[i]:=1;

js(i);

c[i]:=0;

p:=dg(i);

q[i]:=p;

if o>p then o:=p;

end;

writeln(o);

for i:=1 to n do if q[i]=o then write(i,’ ’);

end.

#1 cszqwe@2009-10-22 21:36:00
回复 删除
算法貌似没错,不会是时间复杂度太高爆掉了吧!

本人山东一小菜,请求牛们指点迷津

这是到树形dp,小树据动能过

救救我吧

#2 renqing@2009-10-23 03:22:00
回复 删除
请问程序自己写错了就是测评机火星了吗?
#3 sesame@2009-10-23 07:00:00
回复 删除
那个... 貌似..如果没输出机子 就会认为是上一次的结果..(不知道对不对..)
查看更多回复
提交回复