原题地址：http://www.rqnoj.cn/problem/5
解题思路：
今天刚刚才知道了区间DP。。Orz。。本来以为是状态压缩DP，后来看到数据量才发现原来不是。后来参考了别人的题解。自己整理了思路：
问题现在变成从一堆数里面按某个顺序取走一些数，每次取走一个数的时候会得到能量，求最大能获得的能量。
由于是环状的，先将序列延长一倍，第n个数字等于第0个数字，第n+1个数字为第1个数字...依次类推。
a[i]表示第i个数
状态表示：
DP[i][j]表示在区间[i,j]中，除了a[i]之外的其他数都取走的最大的能量。（即最后留下的数是a[i]）那么最后要求的答案就是假设最后剩下的是a[i]（0<=i<n）这n中情况中的的最大值。
初始状态：DP[i][j]=0。
状态转移方程：DP[i][j]=max{ a[i]*a[k+1]*a[j+1]+DP[i][k]+DP[k+1][j] } (i<=k<j)
解题代码：
#include<stdio.h>
#include<iostream>
using namespace std;
int a[],dp[][]={};
int Max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n,i,j,k;
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%d",&a[i]);
a[i+n]=a[i];
}
for(j=;j<*n-;j++)
{
for(i=j;i>j-n&&i>=;i--)
{
for(k=i;k<j;k++)
{
dp[i][j]=Max(a[i]*a[k+]*a[j+]+dp[i][k]+dp[k+][j],dp[i][j]);
}
}
}
int ans=;
for(i=;i<n;i++)
{
ans=Max(ans,dp[i][i+n-]);
}
printf("%d\n",ans);
return ;
}