能量项链（环，动归）

http://codevs.cn/problem/1154/

在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。

如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为mrn，新产生的珠子的头标记为m，尾标记为n。

通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请计算一串项链能释放出的最大能量。

---

从i到j的最大能量：

f(i,j)=max{f(i,k)+f(k+1,j)+x[i]x[k+1]x[j+1]}，i<=k<=j-1

注意处理环中i>j的情况，以及j+1越界的情况

---

#include <iostream>
using namespace std;

int x[100],n,cache[100][100];

int max(int i, int j)
{
    if(cache[i][j]!=-1)
        return cache[i][j];

    int big=0, now;
    if(i<j)
    {
        for(int k=i; k<j; k++)
        {
            now= x[i]*x[k+1]*x[(j+1)%n] +max(i,k) +max(k+1,j);
            if(now>big)
                big=now;
        }
    }
    else
    {
        for(int k=i; k<n-1; k++)
        {
            now= x[i]*x[k+1]*x[j+1] +max(i,k) +max(k+1,j);
            if(now>big)
                big=now;
        }
        now= max(i,n-1) +max(0,j) +x[i]*x[0]*x[j+1];
        if(now>big)
            big=now;
        for(int k=0; k<j; k++)
        {
            now= x[i]*x[k+1]*x[j+1] +max(i,k) +max(k+1,j);
            if(now>big)
                big=now;
        }
    }

    cache[i][j]=big;
    return big;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>x[i];

    for(int i=0,j ;i<n;i++)
        for(j=0;j<n;j++)
        {
            if(i==j)
                cache[i][j]=0;
            else
                cache[i][j]=-1;
        }
    cache[n-1][0]=x[n-1]*x[0]*x[1];

    int big=max(0,n-1),now;
    for(int i=1;i<n;i++)
    {
        now=max(i,i-1);
        if(big<now)
            big=now;
    }

    cout<<big;

    return 0;
}