[NOI 1995] 石子合并

知识点

区间动态规划、环形结构、前缀和。

解题思路

复制数组，将圆环展开成长度为2N的序列。任何一种圆环合并方案最后都可以选择一个断点，转化成长度为N的连续区间；枚举这个区间的左端点即可覆盖所有断点。

令mn[l][r]、mx[l][r]分别为将区间[l,r]合并成一堆的最小、最大得分。最后一次合并必定将[l,k]与[k+1,r]这两堆相加，额外得分为原区间石子总数。于是分别对所有k取最小值和最大值。用前缀和O(1)求区间总数，按区间长度从小到大计算。

正确性说明

单堆不需合并，两种状态值都为0。对于更长区间，任意合法方案的最后一步都对应唯一分界k，之前的操作仅发生于左右两个子区间。若某个子区间未采用相应最优方案，替换它可改进总得分，因此最优方案满足上述转移。反过来，每个分界与左右合法方案都能拼成一个合法合并方案，所以转移没有遗漏或引入非法方案。圆环的任意最终分界都包含在N个断点中，对它们取最优值得到圆环答案。

易错点

N=1时两行都应输出0。石子允许为0，不能把0当作“未计算”。最小状态初始值设为足够大的数，最大状态可由0开始，因为所有得分非负。只统计长度N的区间，并在最小值和最大值上分别取最优，不能用一般贪心合并替代相邻合并限制。

复杂度

复制后状态数O(N²)，每个状态枚举O(N)个分界；总时间O(N³)，总空间O(N²)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;cin>>n;
    vector<long long> a(2*n+1),sum(2*n+1);
    for(int i=1;i<=n;++i){cin>>a[i];a[i+n]=a[i];}
    for(int i=1;i<=2*n;++i) sum[i]=sum[i-1]+a[i];
    vector<vector<long long>> mn(2*n+1,vector<long long>(2*n+1));
    vector<vector<long long>> mx=mn;
    for(int len=2;len<=n;++len){
        for(int l=1;l+len-1<=2*n;++l){
            int r=l+len-1;mn[l][r]=LLONG_MAX;
            long long weight=sum[r]-sum[l-1];
            for(int k=l;k<r;++k){
                mn[l][r]=min(mn[l][r],mn[l][k]+mn[k+1][r]+weight);
                mx[l][r]=max(mx[l][r],mx[l][k]+mx[k+1][r]+weight);
            }
        }
    }
    long long bestMin=LLONG_MAX,bestMax=0;
    for(int l=1;l<=n;++l){bestMin=min(bestMin,mn[l][l+n-1]);bestMax=max(bestMax,mx[l][l+n-1]);}
    cout<<bestMin<<'\n'<<bestMax<<'\n';
    return 0;
}