难度：普及+/提高

题目描述

        在一个圆形操场的四周摆放N堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
        试设计出1个算法，计算出将N堆石子合并成1堆的最小得分和最大得分。

输入输出格式

输入格式:

        数据的第1行为正整数N，1≤N≤100，表示有N堆石子。第2行有N个数，分别表示每堆石子的个数。

输出格式:

        输出共2行，第1行为最小得分，第2行为最大得分。

输入输出样例

Sample input

4
4 5 9 4

Sample output

43
54

题解

        题目考察线性动态规划。
        与贪心算法不同的是，本题要求只能合并相邻的两堆石子，环形排布又加大了题目难度。
        一种思路是将已知的序列首尾相接，从中截取长度为n的子序列，来模拟环形。这是因为在环形结构中，若只合并相邻的两个数，最后必有两个数待合并，从这两个数中间剪环为链，容易知这两者是等价的。
        但是期初并不知从何处剪环，故要将所有情况都考虑到，从每个剪环策略中选取最值即可。在这个思路中，从何处截取序列便是剪环的操作。
        假定在一个剪环策略下，令左元素为l，右元素为r。设从x到y的序列合并得分最值为f(x，y)，那么可列出状态转移方程(设value(l，r)表示l到r的石子总和):

        规定f(x，x)=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
#include<iostream>

using namespace std;
int n, minAns = 1e9, maxAns = 0;
int op[250] = {0}, sum[250] = {0};
int vis1[250][250] = {0}, vis2[250][250] = {0};

int DP1(int l, int r) {
    if (l == r)return 0;
    if (vis1[l][r] != 0)return vis1[l][r];
    int minn = 1e9;
    for (register int i = l; i < r; i++)minn = min(DP1(l, i) + DP1(i + 1, r), minn);
    return vis1[l][r] = minn + sum[r] - sum[l - 1];
}

int DP2(int l, int r) {
    if (l == r)return 0;
    if (vis2[l][r] != 0)return vis2[l][r];
    int maxn = 0;
    for (register int i = l; i < r; i++)maxn = max(DP2(l, i) + DP2(i + 1, r), maxn);
    return vis2[l][r] = maxn + sum[r] - sum[l - 1];
}

int main() {
    cin >> n;
    for (register int i = 1; i <= n; i++) {
        cin >> op[i];
        op[i + n] = op[i];
    }
    sum[1] = op[1];
    for (
            register int i = 2;
            i <= 2 * n;
            i++)
        sum[i] = sum[i - 1] + op[i];
    for (register int i = 1; i <= n; i++) {
        minAns = min(minAns, DP1(i, i + n - 1));
        maxAns = max(maxAns, DP2(i, i + n - 1));
    }
    cout << minAns << endl << maxAns;
    return 0;
}