算法设计与分析 SCAU11078 不能移动的石子合并（优先做）

11078 不能移动的石子合并（优先做）

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题 语言: G++;GCC;VC;JAVA

Description

做如下两个模型的石子合并，如下模型石子都不能移动出列，且合并都仅发生在相邻两堆石子中：

（1）第一个模型：一行排列且相邻合并
有n堆石子A1,A2,…,An形成一行，每堆石头个数记为ai(1<=i<=n)，相邻两堆可合并，合并的分值为新堆的
石子数。求合并为一堆的最低得分和最高得分。

（2）第二个模型：一圈排列且相邻合并
有n堆石子A1,A2,…,An形成首位相连的一个环形，An和A1相邻，每堆石头个数记为ai(1<=i<=n)，相邻两堆
可合并，合并的分值为新堆的石子数。求合并为一堆的最低得分和最高得分。

例如4堆石子，每堆石子个数：9 4 4 5
若排成一行，最小分值：(4+4)+(8+5)+(9+13)=43，最大分值：(9+4)+(13+4)+(17+5)=52。
若排成圈状，最小分值：(4+4)+(8+5)+(9+13)=43，最大分值：(9+5)+(14+4)+(18+4)=54。

此题以第一模型的最低得分为例，很多同学想着采用总是从最小的相邻两堆下手的思想，认为最后获得的也就是最
低得分。但这个贪心策略是不对的。如下反例：

石子：9 4 6 1 5

贪心策略：
9 4 6 6 计分6
9 10 6 计分10
9 16 计分16
25 计分25
得分共计：6+10+16+25=57

但9 4 6 1 5 若如下方式合并：
13 6 1 5 计分13
13 6 6 计分6
13 12 计分12
25 计分25
13+6+12+25=56

或
9 4 6 6 计分6
9 4 12 计分12
13 12 计分13
25 计分25
6+12+13+25=56

后两种方式合并出的56都比贪心策略的57来的更低，因为总选择最小的相邻两堆去合并，并不能保证后续每步
都可以最小，也许这轮最小导致后续几轮分值较大。

输入格式

两行。第一行n，第二行a1 a2 … an，每个ai(1<=i<=n)表示第i堆石子的个数，n<=100

输出格式

两行。第一行是第一个模型的最低得分和最高得分，中间空格相连，第二行是第二个模型的最低得分和
最高得分，中间空格相连。

输入样例

4
9 4 4 5

输出样例

43 52
43 54

解题思路

这题分为两种情况，一种是链状石子合并，一种是环装石子合并。
链状石子合并可见该文章：算法设计与分析 SCAU19182 石子合并（基础版）

那环装石子合并如何解决呢？

• 其实思路很简单，将环切开就成为链状石子合并，此时就可以用链状石子合并的解题思路来写算法了。
• 如图，如果长度为5的环，切5次即可，成为五种链。

如何切割？

如果直接在链式石子合并算法基础上，最外层加一层用于切割的 for 循环，会导致因为时间复杂度从 n^3 升级成 n^4 而超时，所以我们思路应该稍稍转变一下。

• 将输入数组拷贝一份
• 状态转移完成后，for 循环查找哪个链的代价是符合题目要求的，例如：如图长度原本为5的数组，拓展后输入数组长度变为10，那在 for 循环时可以依次查找如下区间的代价

1. [1, 5]：即链为 1 4 2 5 3
2. [2, 6]：即链为 4 2 5 3 1
3. [3, 7]：即链为 2 5 3 1 4
4. [4, 8]：即链为 5 3 1 4 2
5. [5, 9]：即链为 3 1 4 2 5
6. [6, 10]：即链为 1 4 2 5 3
   
   

1. dp 方程定义

• dp[l][r] 表示从 L 到 R 合并成一堆的最小代价

2. 状态转移方程

此题 dp 思路是将所有区间以及需要的代价全部列出来，那么如何列出来呢？

1. 对于 dp[l][r]：从 L 到 R 合并成一堆的最小代价，我们需要一个指针 mid，放在区间 [l, r] 中间，为什么需要这个 mid 呢？

目的就是将区间按多种情况来进行分割，以找到最符合要求的情况

因此转移方程可以为：dp[l][r] = min(dp[l][r], dp[l][mid] + dp[mid + 1][r] + s[r] - s[l - 1]);

2. dp[l][mid] + dp[mid + 1][r] + s[r] - s[l - 1] 的意义

• 先把区间 [l, r] 切分为两部分 [l, mid] 和 [mid+1, r]，mid 是切分点。
• 再把两部分 [l, mid] 和 [mid+1, r] 合并在一起。
• 注意在进行上一步的同时，还要加上 s[r] - s[l - 1]，也就是合并的代价（通过前缀和来求，即区间和，这段区间加起来的总和）。

3. 转移方程的初值：dp[i][i] = 0，因为合并每堆石子的代价为0，即自己跟自己合并相当于不用合，即最小代价为0

4. 转移方程的最终结果：dp[1, n]：求合并第1堆到第 n 堆石子的最小代价
   
   

3. 算法解题思路

1. 对 dp 数组进行初始化，每个值都初始化为较大的一个数 memset(dp, 0x3f, sizeof(dp));
2. 首先进行数据输入，输入的同时记录前缀和 s[i] = s[i - 1] + a[i]; 以及给转移方程设立初始值 dp[i][i] = 0;
3. 进行状态转移，我们目标是列出所有情况，即各个区间代价和。第一层循环变量为 len：区间长度，第二层循环为 l：区间起点（区间起点终止条件变为了 2 * n），第三层循环为 mid，区间的分割点位置
4. 每次循环时进行决策，跟之前算出过的代价和比较哪个更小，dp[l][r] = min(dp[l][r], dp[l][mid] + dp[mid + 1][r] + s[r] - s[l - 1]);

更多注释可查看下方的完整代码中，有助于理解

代码如下

#include 
#include 
#include 

using namespace std;

int a[301]; // 记录各石堆质量
int s[301]; // 前缀和数组

// dp[i][j] 代表第 i 到 第 j 堆石子的得分
int dp1min[301][301]; // 链式最小得分
int dp1max[301][301]; // 链式最高得分
int dp2min[301][301]; // 环形最小得分
int dp2max[301][301]; // 环形最高得分

int n;

void lian() {
    int len, l, r, mid;

    // len 为区间长度，l(left) 为区间起点，r(right) 为区间终点
    for(len = 2; len <= n; len++) {
        // l的终点为最后一段区间的起点
        for(l = 1; l <= n - len + 1; l++) {
            r = l + len - 1;

            // mid将区间 [l, r] 分成左右两段，所以 mid 不需要等于 r(分不了了)
            for(mid = l; mid < r; mid++) {
                // s[r] - s[l - 1] 为区间 [l, r] 的前缀和，即加起来的总和，合并的代价
                dp1min[l][r] = min(dp1min[l][r], dp1min[l][mid] + dp1min[mid + 1][r] + s[r] - s[l - 1]);
                dp1max[l][r] = max(dp1max[l][r], dp1max[l][mid] + dp1max[mid + 1][r] + s[r] - s[l - 1]);
                //printf("dp[%d][%d]=%d, dp[%d][%d]=%d, dp[%d][%d]=%d s=%d\n", l, r, dp[l][r], l, mid, dp[l][mid], mid + 1, r, dp[mid + 1][r], s[r] - s[l - 1]);
            }
        }
        //printf("len=%d\n\n", len);
    }

    cout << dp1min[1][r] << " " << dp1max[1][r] << endl;

}

void circle() {
    int len, l, r, mid;

    // len 为区间长度，l(left) 为区间起点，r(right) 为区间终点
    for(len = 2; len <= n; len++) {
        // l的终点为最后一段区间的起点
        for(l = 1; l <= 2 * n - len + 1; l++) {
            r = l + len - 1;

            // mid将区间 [l, r] 分成左右两段，所以 mid 不需要等于 r(分不了了)
            for(mid = l; mid < r; mid++) {
                // s[r] - s[l - 1] 为区间 [l, r] 的前缀和，即加起来的总和，合并的代价
                dp2min[l][r] = min(dp2min[l][r], dp2min[l][mid] + dp2min[mid + 1][r] + s[r] - s[l - 1]);
                dp2max[l][r] = max(dp2max[l][r], dp2max[l][mid] + dp2max[mid + 1][r] + s[r] - s[l - 1]);
                //printf("dp2min[%d][%d]=%d, dp2min[%d][%d]=%d, dp2min[%d][%d]=%d s=%d\n", l, r, dp2min[l][r], l, mid, dp2min[l][mid], mid + 1, r, dp2min[mid + 1][r], s[r] - s[l - 1]);
            }
        }
        //printf("len=%d\n\n", len);
    }

    // 由于此题思路是将环转为链式求解，所以具体是要求哪条链得出来的是符合代价要求的(即找环的切割点)
    int resMin = 1000001, resMax = -0x3f;
    for(int i = 1; i <= n; i++) {
        resMin = min(resMin, dp2min[i][i + n - 1]);
        resMax = max(resMax, dp2max[i][i + n - 1]);
    }

    cout << resMin << " " << resMax << endl;
}

int main()
{
    memset(dp1min, 0x3f, sizeof(dp1min));//先把 dp 里的所有数变成一个很大的数
    memset(dp1max, -0x3f, sizeof(dp1max));//先把 dp 里的所有数变成一个很小的数
    memset(dp2min, 0x3f, sizeof(dp2min));//先把 dp 里的所有数变成一个很大的数
    memset(dp2max, -0x3f, sizeof(dp2max));//先把 dp 里的所有数变成一个很小的数

    int i;
    cin >> n;

    s[0] = 0; // 初始化用于后续记录

    for(i = 1; i <= n; i++) {
        cin >> a[i];
        a[i + n] = a[i]; // 复制一遍 a数组，因为环形所以乘个2
    }

    for(i = 1; i <= 2 * n; i++) {
        s[i] = s[i - 1] + a[i]; // 记录前缀和
        dp1min[i][i] = 0; // 自己跟自己合并相当于不用合，即最小代价为0
        dp1max[i][i] = 0; // 自己跟自己合并相当于不用合，即最小代价为0
        dp2min[i][i] = 0; // 自己跟自己合并相当于不用合，即最小代价为0
        dp2max[i][i] = 0; // 自己跟自己合并相当于不用合，即最小代价为0
    }

    lian();
    circle();

    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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101