[NOI1995] 石子合并
题目描述
在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法,计算出将 $N$ 堆石子合并成 $1$ 堆的最小得分和最大得分。
输入格式
数据的第 $1$ 行是正整数 $N$，表示有 $N$ 堆石子。
第 $2$ 行有 $N$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 堆石子的个数。
输出格式
输出共 $2$ 行，第 $1$ 行为最小得分，第 $2$ 行为最大得分。
样例 #1
样例输入 #1
4
4 5 9 4
样例输出 #1
43
54
提示
$1\leq N\leq 100$，$0\leq a_i\leq 20$。
区间DP，dp[i][j] 表示合并从i到j堆石子的最大/最小得分。
区间长度len = j - i + 1
最终合并的时候，有且仅有以下的可能
左边1堆，右边len-1堆，
左边2堆，右边len-2堆，
.
.
.
左边len-1堆，右边1堆，
这样就能得到一个状态转移方程
dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j])
当然，最后还要加上合并的代价,用一个前缀和数组sum来计算
dp[i][j] += sum[j] - sum[i-1]
但是，石子是环形摆放的。
有一个处理技巧，把数组扩展到原来的两倍，a[n+1]的地方放a[1], a[n+2]的地方放a[2],…,a[2n]的地方放a[n]。
这样就把一个环分成了若干条链[1,n],[2,n+1],…,[n,2n]
计算的时候数组长度扩展到原来的两倍，统计最值的时候分别统计遍历每条链即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 110*2;
int n;
int a[N];
int sum[N];
int dp[N][N];
int dp2[N][N];
#define inf 1e9
int dfs1(int l,int r) {
if (l > r) return 0;
if (dp[l][r] != -1) {
return dp[l][r];
}
if (r - l + 1 == 1) {
return dp[l][r] = 0;
}
int mini = 10000000;
for (int i = l + 1; i <= r; i++) {
int t1 = dfs1(l,i-1);
int t2 = dfs1(i,r);
mini = min(mini, t1 + t2);
}
return dp[l][r] = mini + a[r] - a[l-1];
}
int dfs2(int l,int r) {
if (l > r) return 0;
if (dp2[l][r] != -1) {
return dp2[l][r];
}
if (r - l + 1 == 1) {
return dp2[l][r] = 0;
}
int mx = 0;
for (int i = l + 1; i <= r; i++) {
int t1 = dfs2(l,i-1);
int t2 = dfs2(i,r);
mx = max(mx, t1 + t2);
}
return dp2[l][r] = mx + a[r] - a[l-1];
}
int main() {
ios::sync_with_stdio(0),cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i+n] = a[i]; // 注意是环，所以用2n
}
for (int i = 1; i <= 2*n; i++) {
a[i] += a[i-1];
}
for (int i = 1; i <= 2*n; i++) {
for (int j = 1; j <= 2*n; j++) {
dp[i][j] = -1;
dp2[i][j] = -1;
}
}
dfs1(1,2*n);
int ans = inf;
for (int i = 1; i <= n; i++) {
ans = min(ans,dp[i][i+n-1]);
}
cout << ans << endl;
dfs2(1,2*n);
ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans,dp2[i][i+n-1]);
}
cout << ans << endl;
return 0;
}