题解 | #能量项链#

解题思路：

• 因为题是一个项圈构成了环，所以使用两倍的长度存储能量项链$v[2\ast n]v[2*n]$。
• 令$d{p}_{i,j}dp\_\{i,j\}$表示从下标$ii$ 到 下标$jj$这一段合并所释放的能量。合并的长度由小到 大进行$2\to n2\; \backslash to\; n$。枚举每一段区间比较求得最大值。则有状态转移方程：$d{p}_{i,j}=d{p}_{i,k}+d{p}_{k+1,j}+v_i\ast v_{k+1}\ast v_{j+1}dp\_\{i,j\}\; =\; dp\_\{i,k\}+dp\_\{k+1,j\}\; +\; v\_i\; *\; v\_\{k+1\}\; *\; v\_\{j+1\}$。
• 没有看懂请手推一遍合并能量的计算公式。相邻两个合并$merg(i,j)=v_i\ast v_j\ast v_{j+1}merg(i,j)\; =\; v\_i\; *\; v\_j\; *\; v\_\{j+1\}$合并以后只剩下$v_i,v_{j+1}v\_i,v\_\{j+1\}$

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> v(2*n);//开两倍的空间来存储环
    vector<vector<int>> dp(2*n,vector<int>(2*n));
    for(int i = 0; i < n; ++i) {
        cin>>v[i];
        v[n+i] = v[i];
    }
    for(int len = 2; len <= n; ++len){//枚举合并长度
        for(int i = 0; i < 2*n - 1; ++i){
            int j = i + len -1;
            if(j >= 2 * n - 1) break;
            for(int k = i; k < j; ++k){//枚举当前长度下的每一种合并，取最大值
                dp[i][j] = max(dp[i][j], (dp[i][k] + dp[k+1][j] + v[i] * v[k+1]*v[j+1])%1000000007);
            }
        }
    }
    int mx = 0;
    for(int i = 0; i < n; ++i){//枚举所有长度为n的合并情况，取出最大值输出
        mx = max(mx, dp[i][i+n-1]);
    }
    cout<<mx<<endl;
    return 0;
}