NOI1995：石子合并

题目链接

[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
2

样例输出 #1

43
54
1
2

提示

$1\le N\le 100$，$0\le a_i\le 20$。

算法思想

每次只能选相邻的 $2$ 堆合并成新的一堆，以每次合并为阶段进行区间型动态规划，以最小得分为例：

• 状态表示：$f[i][j]$表示从第$i$堆石子一直合并到第$j$堆石子的最小得分
• 状态计算：根据最后一次合并的位置可以分为下面几种情况：
  • 将第$i$堆石子和后面已经完成的$[i+\mathrm{1...}j]$这堆石子合并，得到的分数为$f[i][i]+f[i+1][j]+s[i...j]$
  • 将前面已经完成合并的$[i...i+1]$这堆石子和后面已经完成的$[i+\mathrm{2...}j]$这堆石子合并，得到的分数为$f[i][i+1]+f[i+2][j]+s[i...j]$
  • …
  • 将前面已经完成合并的$[i...k]$这堆石子和后面已经完成的$[k+\mathrm{1...}j]$这堆石子合并，得到的分数为$f[i][i+1]+f[i+2][j]+s[i...j]$
  • …
  • 将前面已经完成合并的$[i...j-1]$这堆石子和第$j$堆石子合并，得到的分数为$f[i][j-1]+f[j][j]+s[i...j]$

$f[i][j]$为以上情况的最小值。其中$s[i...j]$表示本次合并得到的分数，也就是第$i$堆石子到第$j$堆石子的分数和，可以使用前缀和计算得到。

• 初始状态：为计算最小值$f[i][j]$应初始化为无穷大；$f[i][i]$表示就合并自己，初始值为0。

除此之外，由于是在一个圆形操场的四周摆放 $N$ 堆石子，也就是说可以从任何一点出发进行合并。因此，需要采用拆环为链的方式进行处理，最后求以任意起点开始分数的最小值。

时间复杂度

状态数为$n\times n$，状态计算时需要枚举最后一次合并位置，因此时间复杂度为$O(n^3)$。

代码实现

#include 
#include 
#include 
using namespace std;
const int N = 110 * 2, INF = 0x3f3f3f3f;
int f[N][N], g[N][N];
int a[N], s[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) 
    {
        cin >> a[i];
        a[n + i] = a[i]; //拆环为链
    }
    //计算前缀和
    for(int i = 1; i < 2 * n; i ++) s[i] = s[i - 1] + a[i];
    //枚举每次合并的长度，最小长度为2    
    for(int len = 2; len <= n; len ++)
        for(int i = 1; i + len - 1 < 2 * n; i ++) //枚举开始合并的位置
        {
            int j = i + len - 1; //合并结束的位置
            f[i][j] = INF; //初始状态
            //枚举最后一次合并的位置k
            for(int k = i; k < j; k ++)
            {
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]); //最小得分
                g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + s[j] - s[i - 1]); //最大得分
            }
        }
    
    int minx = 1e9, maxx = 0;
    for(int i = 1; i <= n; i ++) //枚举合并起点
    {
        minx = min(minx, f[i][i + n - 1]);
        maxx = max(maxx, g[i][i + n - 1]);
    }
    cout << minx << '\n' << maxx;
    
    return 0;
}
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