我用f[i][j]代表从第i颗合并到j颗的最大值，t代表每次合并的颗数，每次i从0到n-1，j=(i+t-1)%n，最后在f[0][n-1],f[1][0],f[2][1]……f[n-1][n-2]中找最大的值，为什么只能过一般的数据？？

#include<stdio.h>

int main()

{

int t,k,n,i,j,max,temp,f[100][100],r[101]；

scanf("%d",&n)；

for(i=0；i<n；i++){

scanf("%d",&r[i])；

f[i][i]=0；

}

r[i]=r[0]；

for(t=2；t<=n；t++)

for(i=0；i<n；i++){

j=(i+t-1)%n；

max=f[i][i]+f[(i+1)%n][j]+r[i]*r[i+1]*r[j+1]；

k=(i+1)%n；

while(k!=j){

temp=f[i][k]+f[(k+1)%n][j]+r[i]*r[k+1]*r[j+1]；

if(temp>max)

max=temp；

k=(k+1)%n；

}

f[i][j]=max；

}

for(i=1；i<n；i++){

max=f[0][n-1]；

if(f[i][i-1]>max)

max=f[i][i-1]；

}

printf("%d\n",max)；

return 0；

}

只过了一半的数据，没人回答吗

AC了！

同胞啊。

Program EnergyNecklace(Input,Output);

Const

NMax=100;

NMin=4;

Var

Ans : INT64;

N,i,j,k,l,r : Integer;

A : Array[1..Nmax] of Integer;

F : Array[1..Nmax,1..Nmax] of Longint;

Function Spa(x:Integer):Integer;

Begin

If x>N Then x:=x-N;

Spa:=x;

End;

Function Max(x,y:Longint):Longint;

Begin

If x>y

Then Max:=x

Else Max:=y;

End;

Begin

Readln(N);

For i:=1 to N Do

Read(A[i]);

Fillchar(F,Sizeof(F),0);

For l:=2 to N Do

For i:=1 to N Do

Begin

j:=i+l-1;j:=Spa(j);

For k:=1 to l-1 do

Begin

r:=i+k-1;r:=Spa(r);

F[i,j]:=Max(F[i,j],F[i,r]+F[r+1,j]+A[i]*A[Spa(r+1)]*A[Spa(j+1)]);

End;

End;

Ans:=0;

For i:=1 to N Do

Begin

j:=i+N-1;

j:=Spa(j);

If F[i,j]>Ans

Then Ans:=F[i,j];

End;

Writeln(Ans);

End.

过了80

搞半天还是不够Spa，循环就是要Spa到底

Spa万岁！AC咯。

Program EnergyNecklace(Input,Output);

Const

NMax=100;

NMin=4;

Var

Ans : INT64;

N,i,j,k,l,r : Integer;

A : Array[1..Nmax] of Integer;

F : Array[1..Nmax,1..Nmax] of Longint;

Function Spa(x:Integer):Integer;

Begin

If x>N Then x:=x-N;

Spa:=x;

End;

Function Max(x,y:Longint):Longint;

Begin

If x>y

Then Max:=x

Else Max:=y;

End;

Begin

Readln(N);

For i:=1 to N Do

Read(A[i]);

Fillchar(F,Sizeof(F),0);

For l:=2 to N Do

For i:=1 to N Do

Begin

j:=i+l-1;j:=Spa(j);

For k:=1 to l-1 do

Begin

r:=i+k-1;r:=Spa(r);

F[i,j]:=Max(F[i,j],F[i,r]+F[Spa(r+1),j]+A[i]*A[Spa(r+1)]*A[Spa(j+1)]);

//注意啊，r+1那个地方也要Spa一下

End;

End;

Ans:=0;

For i:=1 to N Do

Begin

j:=i+N-1;

j:=Spa(j);

If F[i,j]>Ans

Then Ans:=F[i,j];

End;

Writeln(Ans);

End.