能量项链

P1063 [NOIP2006 提高组] 能量项链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

• 区间dp
• 处理环形将原数据复制一份到后面再dp，最终答案在取最大的
• 三层for循环，第一层迭代间隔，第二层迭代左右区间，第三层迭代中间的分隔位置
• 转移方程看能否更新成左子区间加右子区间加两个子区间合并时的结果

#include <bits/stdc++.h>
using namespace std;
#define N 1e5
#define INF 2e9
#define MAX 1005
// https://www.luogu.com.cn/problem/P1063
int dp[MAX][MAX], v[MAX];
int n;
void input()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", v + i);
        v[i + n] = v[i];
    }
}

int main()
{
    input();
    for (int step = 2; step <= n; step++)
    {
        for (int left = 1, right = left + step; right <= n * 2; left++, right++)
        {
            for (int k = left + 1; k <= right - 1; k++)
            {
                dp[left][right] = max(dp[left][right], dp[left][k] + dp[k][right] + v[left] * v[right] * v[k]);
            }
        }
    }
    int maxx = 0;
    for (int i = 1; i <= n; i++)
    {
        maxx = max(maxx, dp[i][i + n]);
    }
    printf("%d", maxx);
}