能量项链

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 957 字

n颗珠子首尾相连，合并相邻珠释放头×中×尾能

一本通
例

正文

/*
原题：能量项链（NOIP2006，环形区间 DP 求最大释放能量）
题意：n 颗珠子首尾相连，合并相邻珠释放 头×中×尾 能量，求合并成一珠的最大总能量。
思路：断环成链（数组扩为 2n），令 b[i] 为第 i 颗珠子头标记、尾为 b[i+1]；
      dp[i][j]=max{dp[i][k]+dp[k+1][j]+b[i]*b[k+1]*b[j+1]}，单珠 dp=0。
复杂度：时间 O(n^3)，空间 O(n^2)
易错点：环形要复制成 2n；合并区间 [i,j] 的左标记是 b[i]、右标记是 b[j+1]。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int> b(2*n+1);
    for(int i=1;i<=n;i++){
        cin>>b[i];
        b[i+n]=b[i];
    }
    vector<vector<long long>> dp(2*n+1, vector<long long>(2*n+1,0));
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=2*n;i++){
            int j=i+len-1;
            for(int k=i;k<j;k++){
                dp[i][j]=max(dp[i][j], dp[i][k]+dp[k+1][j]+(long long)b[i]*b[k+1]*b[j+1]);
            }
        }
    }
    long long ans=0;
    for(int i=1;i+n-1<=2*n;i++){
        ans=max(ans, dp[i][i+n-1]);
    }
    cout<<ans<<"\n";
    return 0;
}

能量项链

正文

一本通·提高篇的其它内容