测评机: 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开始,理解有些别扭,不过不是这个的问题,是不是我的状态缺了?
这样显然很高,其实我们可以将这条链延长2倍,扩展成2n-1堆,其中第1堆与n+1堆完全相同,第i堆与n+i堆完全相同,这样我们只要对这2n堆动态规划后,枚举f(1,n),f(2,n+1),…,f(n,2n-1)取最优值即可即可。时间复杂度为O(8n3)。但是你没有考虑到项链是一个圈。