挺好玩的一道題。。。
NOIP2006的第一題。
在Mars星球上，每個(gè)Mars人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有N顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。并
且，對(duì)于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因?yàn)橹挥羞@樣，通過吸盤（吸盤是Mars人吸收能量的一種器官）的作用，這兩顆
珠子才能聚合成一顆珠子，同時(shí)釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標(biāo)記為m，尾標(biāo)記為r，后一顆能量珠的頭標(biāo)記為r，尾標(biāo)記為n，則聚合后
釋放的能量為m*r*n（Mars單位），新產(chǎn)生的珠子的頭標(biāo)記為m，尾標(biāo)記為n。
需要時(shí)，Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項(xiàng)鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請(qǐng)你設(shè)計(jì)一個(gè)聚合順序，使一串項(xiàng)鏈釋放出的總能量最大。
例如：設(shè)N=4，4顆珠子的頭標(biāo)記與尾標(biāo)記依次為(2，3) (3，5) (5，10) (10，2)。我們用記號(hào)⊕表示兩顆珠子的聚合操作，(j⊕k)表示第j，k兩顆珠子聚合后所釋放的能量。則第4、1兩顆珠子聚合后釋放的能量為：
(4⊕1)=10*2*3=60。
這一串項(xiàng)鏈可以得到最優(yōu)值的一個(gè)聚合順序所釋放的總能量為
((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。
【輸入文件】
輸入文件energy.in的第一行是一個(gè)正整數(shù)N（4≤N≤100），表示項(xiàng)鏈上珠子的個(gè)數(shù)。第二行是N個(gè)用空格隔開的正整數(shù)，所有的數(shù)均不超過
1000。第i個(gè)數(shù)為第i顆珠子的頭標(biāo)記（1≤i≤N），當(dāng)i<N<
span>時(shí)，第i顆珠子的尾標(biāo)記應(yīng)該等于第i+1顆珠子的頭標(biāo)記。第N顆珠子的尾標(biāo)記應(yīng)該等于第1顆珠子的頭標(biāo)記。
至于珠子的順序，你可以這樣確定：將項(xiàng)鏈放到桌面上，不要出現(xiàn)交叉，隨意指定第一顆珠子，然后按順時(shí)針方向確定其他珠子的順序。
【輸出文件】
輸出文件energy.out只有一行，是一個(gè)正整數(shù)E（E≤2.1*109），為一個(gè)最優(yōu)聚合順序所釋放的總能量。
【輸入樣例】
4
2 3 5 10
【輸出樣例】
710
#include <iostream>
using namespace std;
#define MAX 100
int n;//數(shù)量
int f[MAX][MAX];
int a[MAX];//a[i]為第i個(gè)珠子的值
int k,i,j,r,tmp;
int max(int x,int y)
{
if (x>y) return x;
return y;
}
int main()
{
cin >>n;
for (i=0;i<n;++i)
{
cin >>a[i];
}
for(i=2;i<=n;i++)
for(j=0;j<n;j++)
{
k=(i+j)%n;
for(r=1;r<i;r++)
f[j][k]=max(f[j][(j+r)%n]+f[(j+r)%n][k]+a[j]*a[(j+r)%n]*a[k],f[j][k]);
}
tmp=-1;
for(i=0;i<n;i++)
if(f[i][i]>tmp)tmp=f[i][i];
cout<<tmp<<endl;
system("pause");
return 0;
}