记录编号	168565	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]能量项链	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.022 s
提交时间	2015-07-05 17:46:18	内存使用	0.42 MiB

#include<iostream>
#include<cstdlib>
#include<fstream> 
  
using namespace std;
  
const int MAXN = 101;
int n, mar[MAXN * 2], m[MAXN * 2][MAXN * 2] = {0}, ans = 0;
ifstream fi("energy.in");
ofstream fo("energy.out");
#define cin fi
#define cout fo
  
main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> mar[i];
        
        mar[i + n] = mar[i];
    }      
    for(int len = 2; len <= n; len ++)
        for(int i = 1; i <= 2 * n - len + 1; i ++)
        {
            int j = i + len - 1, maxx = 0;
            for(int k = i; k < j; k ++)
            {
                maxx=m[i][k]+m[k+1][j]+mar[i]*mar[k+1]*mar[j+1];
                m[i][j] = max(maxx, m[i][j]);
            }
        }
      
    for(int ia = 1; ia <= n; ia ++)
        ans = max(ans, m[ia][ia + n - 1]);
        
    cout << ans/* << endl*/;
}