题意： 给你一个 含有 n 个珠子的项链，规定只有相邻的珠子才能合到一起并得到能量，合到一起的到的新的珠子，可以和其相邻的珠子继续合成，前后次序没有要求，
问你最大能的到多大的能量；
分析 ：用 dp[i][j]来表示从 i 到 j 合成得到的最大能量，则状态转移方程为
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+a[i].left*a[k].right*a[j].right)
通过枚举 I 和 J 的分割点来得到 dp[i][j]的最大值。
View Code
#include<stdio.h>#include<string.h>#define max(a,b)(a)>(b)?a:bstruct node{int left;int right;}a[202];int dp[203][203];int main(){int n,i,j,k,max;//freopen("D:ce.txt","r",stdin);while(scanf("%d",&n)!= EOF){for(i=1;i<=n;i++)scanf("%d",&a[i].left);for(i=1;i<n;i++)a[i].right=a[i+1].left;a[n].right=a[1].left;for(i=n+1;i<=2*n;i++){a[i].left=a[i-n].left;a[i].right=a[i-n].right;}memset(dp,0,sizeof(dp));for(k=1;k<n;k++)for(i=1;i+k<=2*n;i++)for(j=i+1;j<=i+k;j++)dp[i][i+k]=max(dp[i][i+k],dp[i][j-1]+dp[j][i+k]+a[i].left*a[j].left*a[i+k].right);max=0;for(i=1;i<=n;i++)if(dp[i][i+n-1]>max)max=dp[i][i+n-1];printf("%d\n",max);}return 0;}
