题解 | 能量项链

#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0);
typedef long long LL;

const int mod=1e9+7;
int n;
int main()
{
    IOS
    cin>>n;
    //处理环形问题的技巧：复制一份放后面
    vector<int> a(n+n);
    for(int i=0; i<n; i++)
        cin>>a[i], a[i+n]=a[i];
    
    vector<vector<LL>> dp(n+n, vector<LL>(n+n));

    for(int len=2; len<=n; len++)
        for(int l=0; l<n; l++){
            int r=l+len;    //r其实是后继
            for(int j=l+1; j<r; j++){
                dp[l][r]=max(dp[l][r], dp[l][j]+dp[j][r]+(LL)a[l]*a[j]*a[r]);//[j,r]尾标是a[r]
            }
            if(r<n) dp[l+n][r+n]=dp[l][r];
        }
    
    LL ans=0;
    for(int l=0; l<n; l++) ans=max(ans, dp[l][l+n]);
    cout<<ans%mod;
    return 0;
}

首先这是环状问题，平铺成线性问题只需在后面复制一份数组，截取长度为n的数组即为环的形式。[j,r]尾标是a[r]

区间长度从2到len，l是合并左端点，r是合并右端点的后继（因为要用到尾标记的值）

答案是dp[l][l+n]里的最大值

#牛客春招刷题训练营#