【問題描述】
在Mars星球上，每個Mars人都隨身佩帶著一串能量項鏈。在項鏈上有N顆能量珠。能量珠是一顆有頭標記與尾標記的珠子，這些標記對應著某個正整數(shù)。并且，對于相鄰的兩顆珠子，前一顆珠子的尾標記一定等于后一顆珠子的頭標記。因為只有這樣，通過吸盤（吸盤是Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標記為m，尾標記為r，后一顆能量珠的頭標記為r，尾標記為n，則聚合后釋放的能量為（Mars單位），新產(chǎn)生的珠子的頭標記為m，尾標記為n。
需要時，Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請你設計一個聚合順序，使一串項鏈釋放出的總能量最大。
例如：設N=4，4顆珠子的頭標記與尾標記依次為(2，3) (3，5) (5，10) (10，2)。我們用記號⊕表示兩顆珠子的聚合操作，(j⊕k)表示第j，k兩顆珠子聚合后所釋放的能量。則第4、1兩顆珠子聚合后釋放的能量為：
(4⊕1)=10*2*3=60。
這一串項鏈可以得到最優(yōu)值的一個聚合順序所釋放的總能量為
((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。
【輸入文件】
輸入文件energy.in的第一行是一個正整數(shù)N（4≤N≤100），表示項鏈上珠子的個數(shù)。第二行是N個用空格隔開的正整數(shù)，所有的數(shù)均不超過1000。第i個數(shù)為第i顆珠子的頭標記（1≤i≤N），當i時，第i顆珠子的尾標記應該等于第i+1顆珠子的頭標記。第N顆珠子的尾標記應該等于第1顆珠子的頭標記。
至于珠子的順序，你可以這樣確定：將項鏈放到桌面上，不要出現(xiàn)交叉，隨意指定第一顆珠子，然后按順時針方向確定其他珠子的順序。
【輸出文件】
輸出文件energy.out只有一行，是一個正整數(shù)E（E≤2.1*109），為一個最優(yōu)聚合順序所釋放的總能量。
【輸入樣例】
4
2 3 5 10
【輸出樣例】
710
和石子合并相似的一道動態(tài)規(guī)劃：設狀態(tài)dp[i,j]為從第i顆珠子開始選取j顆連續(xù)的珠子所獲得的最大能量，有狀態(tài)轉移方程dp[i,j]=max(dp[i,k]+dp[x,j-k]+ball[i].head*ball[x].head*ball[y].rear，其中1<=k<j，x=i+k(如果x>=n,x=x-n)，y=x+(j-k)-1(如果y>=n,y=y-n)；初始狀態(tài)dp[i][1]=0，其中1<=i<=n。最后所求的最大值便是dp[i][n]中的最大值，其中1<=i<=n。
#include <iostream>
const int MAXN = 101;
struct ball
{
int head,rear;
}b[MAXN];
int dp[MAXN][MAXN];
int main(){
int i,j,k,x,y,t,v,n,max;
while(scanf("%d",&n)!=EOF){
for(i=1;i<=n;i++){
scanf("%d",&v);
b[i].head=v;
if(i==1) b[n].rear=v;
else b[i-1].rear=v;
dp[i][1]=0;
}
for(j=2;j<=n;j++)
for(i=1;i<=n;i++)
for(dp[i][j]=-1,k=1;k<j;k++){
x=i+k;
if(x>n) x-=n;
y=x+(j-k)-1;
if(y>n) y-=n;
t=dp[i][k]+dp[x][j-k]+b[i].head*b[x].head*b[y].rear;
if(t>dp[i][j]) dp[i][j]=t;
}
for(max=-1,i=1;i<=n;i++)
if(dp[i][n]>max) max=dp[i][n];
printf("%d\n",max);
}
return 0;
}