讨论 / wa了n次了,求解释!!!!!!!
wuzw 2013-07-20 08:35:00
点我顶贴 收藏 删除
状态: Unaccepted

测评机: Xeond[6]

得分: 50分

提交日期: 2013-7-19 18:25:00

有效耗时: 626毫秒

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

测试结果2: 测试结果错误.错误结果为:8015508

正确结果应为:31182687

测试结果3: 通过本测试点|有效耗时62ms

测试结果4: 通过本测试点|有效耗时157ms

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

正确结果应为:54922956

测试结果6: 通过本测试点|有效耗时62ms

测试结果7: 通过本测试点|有效耗时157ms

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

正确结果应为:129341576

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

正确结果应为:328479464

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

正确结果应为:1940277798

var f:array[0..99,0..99]of longint;//

h,t:array[0..99,0..99]of byte;

e:longint;

i,j,k,n:byte;

function shiji(i:byte):byte;//循环珠子,从0开始

begin

if i>n-1 then shiji:=i-n

else shiji:=i;

end;

begin

readln(n);

for i:=0 to n-1 do read(h[i,0]);

for i:=0 to n-2 do t[i,0]:=h[i+1,0];

t[n-1,0]:=h[0,0];

for i:=1 to n-1 do

for j:=0 to n-1 do

begin

h[j,i]:=h[j,0];

t[j,i]:=t[shiji(j+i),0];//觉得是这里错了,但不知为何,求具体解释

end;

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

e:=0;

for i:=1 to n-1 do

for j:=0 to n-1 do

for k:=0 to i-1 do

begin

if f[j,i]<f[j,k]+f[shiji(j+k+1),i-1-k]+h[j,k]*t[j,k]*t[shiji(j+k+1),i-1-k]

then

begin

f[j,i]:=f[j,k]+f[shiji(j+k+1),i-1-k]+h[j,k]*t[j,k]*t[shiji(j+k+1),i-1-k];

if e<f[j,i] then e:=f[j,i];//former if e<f[j,k] then e:=f[j,k];

end;

end;

writeln(e);

{for i:=1 to n-2 do begin

for j:=0 to n-1 do write('[',j,'.',i,']:',f[j,i],' ');//

writeln;

end;

}end.

我正转向c++,所以数组从0开始,理解有些别扭,不过不是这个的问题,是不是我的状态缺了?

#1 代开启@2013-07-20 03:42:00
回复 删除
由于项链是一个圈,因此我们可以枚举分开的位置,首先将这个圈转化为链,因此总的时间复杂度为O(n4)。

这样显然很高,其实我们可以将这条链延长2倍,扩展成2n-1堆,其中第1堆与n+1堆完全相同,第i堆与n+i堆完全相同,这样我们只要对这2n堆动态规划后,枚举f(1,n),f(2,n+1),…,f(n,2n-1)取最优值即可即可。时间复杂度为O(8n3)。但是你没有考虑到项链是一个圈。

#2 wzw@2013-07-20 08:35:00
回复 删除
将h,t数组类型改为integer就行了
查看更多回复
提交回复