program NOIP20061;

var n,i,q,j,max,bj:integer;a:array[1..100]of integer;

m:array[1..100,1..100]of integer;

ss:longint;

begin

read(n);

max:=0;

for i:=1 to n do

begin

read(a[i]);

if a[i]>max

then begin

max:=a[i];

bj:=i;

end;

end;

ss:=0;

for i:=1 to n do

m[i,1]:=a[i];

for i:=bj to n do

begin

inc(q);

m[q,1]:=a[i];

m[q,2]:=i+1;

end;

for i:=1 to bj-1 do

begin

inc(q);

m[q,1]:=a[i];

m[q,2]:=i+1;

end;

m[n,2]:=m[bj,1];

for i:=2 to n-1 do

ss:=ss+m[1,1]*m[i,1]*m[i+1,1];

ss:=ss+m[1,1]*m[n,1]*m[1,1];

write(ss);

end.

不能用贪心，看一下相关题解吧，这是区域动态规划

不能用贪心，这是区域动态规划。

设链中的第i颗珠子头尾标记为(Si-1与Si)。

令F(i,j)表示从第i颗珠子一直合并到第j颗珠子所能产生的最大能量，则有：

F(i,j)=Max{F(i,k)+F(k+1,j)+Si-1*Sk*Sj, i<=k<j}

边界条件：F(i,i)=0

1<=i<k<j<=n

由于项链是一个圈，因此我们可以枚举分开的位置，首先将这个圈转化为链，因此总的时间复杂度为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)。