[NOIP 2006 提高组] 能量项链

知识点

区间动态规划、环形结构

解题思路

将头标记数组复制一遍，令f[l][r]表示连续珠子l到r全部合并的最大能量。枚举最后合并的分界k，转移f[l][k]+f[k+1][r]+a[l]·a[k+1]·a[r+1]。长度从2到N计算，最终枚举N种起点取最大。

正确性说明

最后一次合并必把当前连续区间分成两个已合并子区间，释放能量只由它们的首尾标记决定。两侧最优子问题独立，枚举分界穷尽所有括号结构。复制数组后每个环形切口都对应某个长度N区间，取最大覆盖全部最优合并方式。

易错点

r+1是尾标记，需要复制到2N+1；不是石子合并的区间和代价；输入还保证答案≤2.1×10^9，计算中仍用64位。

复杂度

时间O(N³)，空间O(N²)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;vector<long long>a(2*n+2);for(int i=1;i<=n;i++)cin>>a[i],a[i+n]=a[i];a[2*n+1]=a[1];vector<vector<long long>>f(2*n+2,vector<long long>(2*n+2));for(int len=2;len<=n;len++)for(int l=1;l+len-1<=2*n;l++){int r=l+len-1;for(int k=l;k<r;k++)f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+a[l]*a[k+1]*a[r+1]);}long long ans=0;for(int i=1;i<=n;i++)ans=max(ans,f[i][i+n-1]);cout<<ans<<'\n';}