讨论 / 那位神牛看一下问题所在
yu990601 2012-05-17 20:57:00
点我顶贴 收藏 删除
program rq_145;

var

a:array[1..10000]of longint;

n:longint;

i,j,max,s,e:longint;

sum:array[1..10000,1..10000]of longint;

fu:boolean;

begin

readln(n);

for i:=1 to n do

begin

read(a[i]);

sum[i,i]:=a[i];

end;

max:=-maxlongint;s:=0;e:=0;

for i:=2 to n do

for j:=1 to n-i+1 do

begin

sum[j,j+i-1]:=sum[j,j+(i-1)div 2]+sum[j+(i-1)div 2+1,j+i-1];

if sum[j,j+i-1]>max then begin

max:=sum[j,j+i-1];

s:=j;e:=j+i-1;

end;

end;

if max<0 then begin writeln(0);halt;end;

writeln(s,' ',e);

writeln(max);

end.

#1 yu990601@2012-05-17 19:20:00
回复 删除
最大子序列和

状态: Unaccepted

测评机: Xeond[6]

得分: 20分

提交日期: 2012-5-18 10:09:00

有效耗时: 641毫秒

测试结果1: 选手程序运行超过时限

测试结果2: 选手程序无输出

测试结果3: 选手程序运行超过时限

测试结果4: 选手程序无输出

测试结果5: 选手程序无输出

测试结果6: 选手程序运行超过时限

测试结果7: 测试结果错误.错误结果为:2791 4289

21554

正确结果应为:1475 1756

9359

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

测试结果9: 选手程序运行超过时限

测试结果10: 通过本测试点|有效耗时547ms

#2 yu990601@2012-05-17 19:20:00
回复 删除
难道是我题意理解错误了?

#3 Sfiction@2012-05-17 20:57:00
回复 删除
为什么要div 2..

最大子序列和不是有O(n)的动态规划解法吗?

查看更多回复
提交回复