Algorithm - Problem - 石子合并

[NOI1995] 石子合并 洛谷 P1880

问题描述

在一个圆形操场的四周摆放 NN 堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的 22 堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。

试设计出算法,计算出将 NN 堆石子合并成 11 堆的最小得分和最大得分.

输入

第1行正整数N,1N100N, 1\leqslant N\leqslant 100,表示有 NN 堆石子.
第2行有NN个数,分别表示每堆石子的个数.

输出

输出共2行,第1行为最小得分,第2行为最大得分.

样例输入
1
2
4
4 5 9 4
样例输出
1
2
43
54

动态规划

分析

设石子数目存储于数组 aa 中,下标从 00 开始.
对于此类环形问题,大多都可采用“化环为链”的手段,即 i:0i<n,a[i+n]=a[i]\forall i:0\leqslant i< n, a[i + n] = a[i],将原先 aa 的所有元素拷贝一份追加到 aa 最后,将环形转化为了线性结构.
此类问题是比较经典的区间 DP,因此我们设 dmin[i][j]d_{min}[i][j] 表示从下标 ii 的石子到下标 jj 的石子合并得分的最小值,类似地 dmax[i][j]d_{max}[i][j] 表示从下标 ii 的石子到下标 jj 的石子合并得分的最大值.
s[i][j]s[i][j] 为下标 ii 的石子到 下标 jj 的石子的加和.
则有如下状态转移方程
dmin[i][j]=min{dmin[i][k]+dmin[k+1][j]+s[i][j]k:ik<j}d_{min}[i][j] = \min\left\{d_{min}[i][k] + d_{min}[k + 1][j] + s[i][j]\bigg|\forall k: i\leqslant k < j\right\}
dmax[i][j]=max{dmax[i][k]+dmax[k+1][j]+s[i][j]k:ik<j}d_{max}[i][j] = \max\left\{d_{max}[i][k] + d_{max}[k + 1][j] + s[i][j]\bigg|\forall k: i\leqslant k < j\right\}
遍历顺序应为第一层 ii2n22n - 200,第二层 jji+1i + 1min{i+n1,2n1}\min\{i + n - 1, 2 * n - 1\},再如上式遍历 kk.

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#define MAXN (100+5)
#define INFTY (-1)
#define BMAX(a,b) (((a)>(b))?(a):(b))
#define BMIN(a,b) (((a)<(b))?(a):(b))

int main()
{
int n;
int a[MAXN * 2];
int sum[MAXN * 2];
int dmin[MAXN * 2][MAXN * 2];
int dmax[MAXN * 2][MAXN * 2];
int tsum;
int rmin = INFTY, rmax = 0;
std::cin >> n;
for(int i = 0; i < n; i++)
{
std::cin >> a[i];
a[i + n] = a[i];
//dmin[i][i] = a[i];
//dmax[i][i] = a[i];
//dmin[i + n][i + n] = a[i];
//dmax[i + n][i + n] = a[i];
}
sum[0] = a[0];
for(int i = 1; i < 2 * n; i++)
{
sum[i] = sum[i - 1] + a[i];
}
for(int i = 2 * n - 2; i >= 0; i--)
{
for(int j = i + 1; (j < i + n) && (j < 2 * n); j++)
{
dmin[i][j] = INFTY;
dmax[i][j] = 0;
if(i >= 1) tsum = sum[j] - sum[i - 1];
else tsum = sum[j];
for(int k = i; k < j; k++)
{
if(dmin[i][j] == INFTY) dmin[i][j] = dmin[i][k] + dmin[k + 1][j] + tsum;
else dmin[i][j] = BMIN(dmin[i][j], dmin[i][k] + dmin[k + 1][j] + tsum);
dmax[i][j] = BMAX(dmax[i][j], dmax[i][k] + dmax[k + 1][j] + tsum);
}
}
}
for(int i = 0; i < n; i++)
{
rmin = (rmin == INFTY) ? (dmin[i][i + n - 1]) : (BMIN(rmin, dmin[i][i + n - 1]));
rmax = BMAX(rmax, dmax[i][i + n - 1]);
}
std::cout << rmin << std::endl << rmax;
}