SDNU 1178.能量项链（区间dp）

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define eps 1e-9
#define pi acos(-1)

const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int maxn = 1000 + 8;

struct node
{
    int m;
}a[maxn];

ll dp[maxn][maxn];
int n;

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i].m;
        a[i + n].m = a[i].m;
    }
    for(int len = 2; len <= n; len++)///长度
    {
        for(int i = 1; i + len - 1 < 2 * n; i++)///起点
        {
            int en = i + len - 1;///终点
            dp[i][en] = -inf;
            for(int k = i; k < en; k++)
                dp[i][en] = max(dp[i][en], dp[i][k] + dp[k + 1][en] + a[i].m * a[k + 1].m * a[en + 1].m);
        }
    }
    ll mi = dp[1][n];
    for(int i = 2; i <= n; i++)
        if(mi < dp[i][i + n - 1])
            mi = dp[i][i + n - 1];
    cout << mi << ‘\n‘;
    return 0;
}
/*

*/