题解 | 能量项链（区间dp）

#牛客春招刷题训练营# + 链接

区间dp经典题啦

先套路复制一遍解环，然后用dp[i][j]表示第i颗到第j颗聚合完之后的最优值，每次枚举最后是哪两段聚合就可以

#include <iostream>
using namespace std;

using ll = long long;
const int mod=1e9+7;
const int N=210;
ll dp[N][N], a[N];

inline void getmax(ll &x, ll y)
{
    if (y>x) x=y;
}

int main() {
    int n,m;
    scanf("%d", &n);
    for (int i=1;i<=n;i++) {
        scanf("%lld", &a[i]);
        a[n+i]=a[i];
    }
    m = n+n;
    a[m+1]=a[1];
    a[m+2]=a[2];
    for (int i=1;i<=m;i++) dp[i][i+1]=a[i]*a[i+1]*a[i+2];
    for (int x=3;x<=n;x++) {
        for (int i=1,j=x;j<=m;i++,j++) {
            for (int k=i;k<j;k++) {
                getmax(dp[i][j], dp[i][k]+dp[k+1][j]+a[i]*a[j+1]*a[k+1]);
            }
        }
    }
    ll ans = 0;
    for (int i=1;i<=n;i++) {
        getmax(ans, dp[i][i+n-1]);
    }
    printf("%lld\n", ans%mod);
    return 0;
}