【题目来源】
洛谷：P1880 [NOI1995] 石子合并 - 洛谷
【题目描述】
在一个圆形操场的四周摆放 \(N\) 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 \(2\) 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法,计算出将 \(N\) 堆石子合并成 \(1\) 堆的最小得分和最大得分。
【输入】
数据的第 \(1\) 行是正整数 \(N\)，表示有 \(N\) 堆石子。
第 \(2\) 行有 \(N\) 个整数，第 \(i\) 个整数 \(a_i\) 表示第 \(i\) 堆石子的个数。
【输出】
输出共 \(2\) 行，第 \(1\) 行为最小得分，第 \(2\) 行为最大得分。
【输入样例】
4
4 5 9 4
【输出样例】
43
54
【算法标签】
《洛谷 P1880 石子合并》 #动态规划DP# #区间DP# #四边形不等式# #NOI#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 205; // 定义最大石子堆数的两倍int n; // 石子堆数
int a[N]; // 存储石子数量的数组（环形展开为两倍长度）
int sum[N]; // 前缀和数组
int f_min[N][N]; // f_min[i][j]表示合并i到j堆的最小得分
int f_max[N][N]; // f_max[i][j]表示合并i到j堆的最大得分
int ans_min = 1e9; // 最小得分结果
int ans_max; // 最大得分结果int main()
{// 输入石子堆数和每堆石子数量cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];a[i + n] = a[i]; // 环形问题展开为两倍长度}// 初始化最小得分数组为极大值memset(f_min, 0x3f, sizeof(f_min));// 初始化前缀和数组和单堆得分为0for (int i = 1; i <= 2 * n; i++){f_min[i][i] = 0; // 单堆不需要合并，得分为0sum[i] = sum[i - 1] + a[i]; // 计算前缀和}// 动态规划处理所有可能的合并区间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++) // 枚举分割点{// 更新最小得分f_min[i][j] = min(f_min[i][j], f_min[i][k] + f_min[k + 1][j] + sum[j] - sum[i - 1]);// 更新最大得分f_max[i][j] = max(f_max[i][j],f_max[i][k] + f_max[k + 1][j] + sum[j] - sum[i - 1]);}}}// 在所有可能的n长度区间中寻找最优解for (int i = 1; i <= n; i++){ans_min = min(ans_min, f_min[i][i + n - 1]);ans_max = max(ans_max, f_max[i][i + n - 1]);}// 输出结果cout << ans_min << endl << ans_max << endl;return 0;
}
【运行结果】
4
4 5 9 4
43
54