# 11073: 【原1073】能量项链

### 题目描述

author: lsz 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1073

NOIP2006提高组

## Sample Input

4
2 3 5 10


## Sample Output

710


## FineArtz's solution

/* 能量项链 */
#include <iostream>
#include <cstring>
using namespace std;

const int INF = 2147483647;

int main(){
int n;
cin >> n;
int a[205], m[205][205];
for (int i = 1; i <= n; ++i){
cin >> a[i];
a[n + i] = a[i];
}
int ans = 0;
for (int t = 0; t <= n - 1; ++t){
memset(m, 0, sizeof(0));
for (int l = 2; l <= n; ++l){
for (int i = t + 1; i <= t + n - l + 1; ++i){
int j = i + l - 1;
m[i][j] = 0;
for (int k = i; k <= j - 1; ++k){
int tmp = m[i][k] + m[k + 1][j] + a[i] * a[k + 1] * a[j + 1];
if (tmp > m[i][j])
m[i][j] = tmp;
}
}
}
if (m[t + 1][t + n] > ans)
ans = m[t + 1][t + n];
}
cout << ans << endl;
return 0;
}


## yyong119's solution

#include <iostream>
#include <cstring>
using namespace std;
int main() {
int n, e[201], e_max[201][201], ans = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> e[i];
e[i + n] = e[i];
}
memset(e_max, 0, sizeof(e_max));
for (int i = 2; i < n * 2; ++i)
for (int j = i - 1; j >= 1 && i - j < n; --j) {
for (int k = j; k < i; ++k) {
int tem = e_max[j][k] + e_max[k + 1][i] + e[j] * e[k + 1] * e[i + 1];
if (tem > e_max[j][i]) e_max[j][i] = tem;
}
if (e_max[j][i] > ans) ans = e_max[j][i];
}
cout << ans << endl;
return 0;
}