P1880 [NOI1995] 石子合并
题目大意
在一个圆形操场上摆放了 NN 堆石子，每次只能选择相邻的两堆合并成一堆，并将新堆的石子数记为该次合并的得分。求将所有石子合并成一堆的最小得分和最大得分。
数据范围： 1≤N≤1001≤N≤100，每堆石子数 ai≤20ai≤20。
分析
这是一个经典的区间DP问题，类似于“合并石子”，但这里是环形排列。
若为直线排列，可直接用区间DP：设 dp[l][r]dp[l][r] 表示合并区间 [l,r][l,r] 的石子得到的最优得分，转移时枚举分割点 kk，将左右合并，再加上本次合并的得分（即区间总和）。
环形结构需要特殊处理：常用技巧是将环形拆成两倍长度的线性序列，即复制一份接在原序列后面，然后对每个长度为 NN 的区间做DP，最后取最值。
由于 N≤100N≤100，O(N3)O(N3) 的区间DP完全可行。
一般思路（区间DP）
- 状态定义
设 f[l][r] 表示合并区间 [l,r] 的石子（即从第 l 堆到第 r 堆）所能得到的最小得分，g[l][r] 表示最大得分。 - 状态转移
当合并区间 [l,r] 时，最后一步一定是将某两堆合并，这两堆分别是由 [l,k] 和 [k+1,r] 合并而成的。因此：
f[l][r]=minf[l][k]+f[k+1][r]+sum(l,r)) 范围l≤k<r
g[l][r]=max(g[l][k]+g[k+1][r]+sum(l,r) 范围l≤k<r
其中 sum(l,r)表示区间 [l,r]的石子总数，可用前缀和快速计算。
3. 初始化
当区间长度为 1 时，无需合并，得分为 0，即 f[i][i]=g[i][i]=0
4. 枚举顺序
按照区间长度从小到大进行DP，保证在计算长区间时，所有子区间已经计算完毕。
环形处理优化
环形问题的一个常用技巧是“破环成链”：将原数组复制一份接在末尾，形成一个长度为 2N 的线性序列。这样，任意一个环形区间（长度为 N）都可以表示为线性序列中某个长度为 NN 的连续区间。我们只需对这 2N 个石子进行DP，计算出所有长度 ≤ N 的区间的最优值，然后取所有长度为 N 的区间的最优值中的最小和最大即可。
这样处理的好处是不需要单独处理环形相邻关系，直接使用线性DP，复杂度不变。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0)
#define pll pair<ll,ll>const ll N = 210;
ll f[N][N],g[N][N];//最小，最大
ll aa[N],ss[N];//石子树，前缀和
void solve(){ll n; cin >> n;for(ll i = 1; i <= n; i++){cin >> aa[i];}for(ll i = 1; i <= n; i++){aa[i + n] = aa[i];}ss[0] = 0;for(ll i = 1; i <= n * 2; i++){ss[i] = ss[i - 1] + aa[i];}memset(f,0x3f,sizeof f);memset(g,-0x3f,sizeof g);for(ll i = 0; i <= 2 * n; i++){f[i][i] = 0;g[i][i] = 0;}for(ll len = 2; len <= n; len++){for(ll l = 1; l + len - 1 <= 2 * n; l++){ll r = l + len - 1;for(ll k = l; k < r; k++){ll cost = ss[r] - ss[l - 1];f[l][r] = min(f[l][r],f[l][k] + f[k + 1][r] + cost);g[l][r] = max(g[l][r],g[l][k] + g[k + 1][r] + cost);}}}ll ans1 = 1e9, ans2 = -1e9;for(ll i = 1; i <= n; i++){ans1 = min(ans1,f[i][i + n - 1]);ans2 = max(ans2,g[i][i + n - 1]);}cout<<ans1<<endl<<ans2<<endl;return;
}int main(){fast;ll t = 1; //cin >> t;while(t--){solve();}return 0;
}