区间DP | 2：环上的合并石子 —— 例题：合并石子（环形）

傷城~ 2023-07-17 07:28 45阅读 0赞

本文是在[区间DP | 1：矩阵链乘问题（含优化） —— 例题：矩阵链乘、合并石子][DP _ 1_ _] 上的升级（建议先看链接文章）。从链到环的改变，但本质还是区间dp问题，将环的区间任然解析成链即可。

>     环上的合并石子问题：环形排列着N堆石子，现在要将石子合并成一堆。规定如下：每次只能将相邻的两堆石子合并，合并两堆石子所花费的时间为两堆石子的数量和。求将N堆石子合并成一堆最小花费的时间。（石子分为n堆，石子的数量存储在数组p[0..n-1]中）

若将此题的环一条条转成线来机械的运算：考虑为 n 个线型的合并石子，时间复杂度上必将增加一个幂次，不够划算，下面有更好的方法。（其实仔细想想，n次调用线型的合并石子的模型，其实存在大量重复计算）

--------------------

**本文****目录**

方法一：直接刚！将数组环形考虑 —— 时间复杂度![O(n^3)][O_n_3]

方法二：化圆为直 —— 时间复杂度![O(n^3)][O_n_3]

方法三： 化圆为直优化版 —— 时间复杂度![\\bg\_white O(n^2)][bg_white O_n_2]

end

--------------------

### 方法一：直接刚！将数组环形考虑 —— 时间复杂度![O(n^3)][O_n_3] ###

既然是环形的，我们将数组环形地去考虑即可，只是因为各种临界问题，代码比较复杂，要注意细节~（实在是太琐碎了！写了两个小时才把bug清理完，流下了惨痛的泪水，所以后又改进了方法，详见方法二）

相较于原方法，核心部分是三层循环，但是由于环形的两端连接问题，第2、3层循环均需要改动：

*  第一层循环：长度 l = 2..n
 *  第二层循环：讨论每个长度为 l 的石子堆 ![p\_\{i..j\}][p_i..j]：i = 1..n， j = ( i + l + 1 ) % n（此循环体内计算sum也是复杂了些，建议单独写出一个calcSum函数计算）
 *  第三层循环：确定最优分割点 k = i..j-1

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][]

两种方法对应的ans数组的填充也是不同的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1][]

**代码实现：**

注意临界问题！注意琐碎的临界问题！十分注意琐碎的临界问题！！！

#define N 100
    
    #include <cstdio>
    #include <algorithm>
    #include <climits>
    using namespace std;
    
    /* 合并石子问题：环形排列着N堆石子，现在要将石子合并成一堆。
     * 规定如下：每次只能将相邻的两堆石子合并，合并两堆石子所花费的时间为两堆石子的数量和。
     * 求将N堆石子合并成一堆最小花费的时间。（石子分为n堆，石子的数量存储在数组p[0..n-1]中）*/
    
    int ans[N][N] = {0};
    int s = 0;  //所有石子堆的总和（提前计算好）
    
    /* 计算p[i..j]的石子总和 (由于是环形，j可以小于i)*/
    int calcSum(int p[], int l, int r, int n) {
        /* 特殊考虑完整（包含了全部石堆）的情况 */
        if (l - r == 1 || r - l + 1 == n)
            return s;
        /* 正常计算 */
        int sum = 0;
        for (int i = l; i != (r + 1) % n; i = (i + 1) % n)
            sum += p[i];
        return sum;
    }
    
    int MergeStone(int p[], int n) {
    
        int min_ans = INT_MAX;
        /* 石子堆的个数：从1到n */
        for (int l = 2; l <= n; l++) {
            /* 讨论l个石子的石子堆 p[i..j](由于是环形，j可以小于i) */
            for (int i = 0; i < n; i++) {
                int j = (i + l - 1) % n;
                int sum = calcSum(p, i, j, n);
                ans[i][j] = INT_MAX;
                /* 依次讨论每一个分割点d:将石子堆p[i..j]分成p[i..k]和 A[k+1..j] */
                for (int k = i; k != j; k = (k + 1) % n)
                    ans[i][j] = min(ans[i][k] + ans[(k + 1) % n][j] + sum, ans[i][j]);
                /* l = n 即我们需要的答案范围，找出最小值 */
                if(l == n) {
                    min_ans = min(ans[i][j], min_ans);
                }
            }
        }
        return min_ans;
    }
    
    int main() {
        int n = 4;
        int p[] = {4, 2, 3, 4};
        for (int i = 0; i < n; i++)
            s += p[i];
        printf("%d\n", MergeStone(p, n));
    }

--------------------

### 方法二：化圆为直 —— 时间复杂度![O(n^3)][O_n_3] ###

为方便遍历，可以考虑化圆为直：把圆形剪开 —— 假设石子堆为1、2、3，那么剪开的石子堆为1、2、3、1、2，那么如果原数组 p 长度为 n， 那么经过我们的剪开操作，长度变为 2n - 1。接下来就是和线型的合并石子问题一样了。

唯一的区别是：对于线型的2n - 1 个石子堆，我们的结果不是选取 L = 2n - 1的，而是 L= n 中所有结果的最小值。

**代码实现：**

（在未改进的线形合并石子问题上改的，故时间复杂度也为![O(n^3)][O_n_3 1]）

#define MAX 100
    
    #include <cstdio>
    #include <climits>
    #include <algorithm>
    
    using namespace std;
    /* 合并石子问题：环形排列着N堆石子，现在要将石子合并成一堆。
     * 规定如下：每次只能将相邻的两堆石子合并，合并两堆石子所花费的时间为两堆石子的数量和。
     * 求将N堆石子合并成一堆最小花费的时间。（石子分为n堆，石子的数量存储在数组p[0..n-1]中）*/
    int ans[2 * MAX][2 * MAX] = {0};
    
    /* 将环形的石子化为线形 */
    void GetList(int p[], int n) {
        int j = 0;
        for (int i = n; i < 2 * n - 1; i++)
            p[i] = p[j++];
    }
    
    int MergeStone(int p[], int n) {
    
        GetList(p, n);  //化圆为直
        int min_ans = INT_MAX;
        int N = 2 * n - 1;// 线形中石子堆个数看做 2n - 1
        /* 石子堆的个数：从1到n */
        for (int l = 2; l <= n; l++) {
            /* 讨论l个石子的石子堆 p[i..j] */
            for (int i = 0; i < N - l + 1; i++) {
                int j = i + l - 1;
                /* 计算石子堆p[i..j]的总数 */
                int sum = 0;
                for (int t = i; t <= j; t++)
                    sum += p[t];
    
                /* 依次讨论每一个分割点d:将石子堆p[i..j]分成p[i..k]和 A[k+1..j] */
                ans[i][j] = INT_MAX;
                for (int k = i; k < j; k++)
                    ans[i][j] = min(ans[i][k] + ans[k + 1][j] + sum, ans[i][j]);
                /* l = n 即我们需要的答案范围，找出最小值 */
                if (l == n) {
                    min_ans = min(ans[i][j], min_ans);
                }
            }
        }
        return min_ans;
    }

--------------------

## 方法三： 化圆为直优化版 —— 时间复杂度![\\bg\_white O(n^2)][bg_white O_n_2] ##

同[区间DP | 1：矩阵链乘问题（含优化） —— 例题：矩阵链乘、合并石子][DP _ 1_ _]中的改进方法，新增最优决策点，存储于divide数组中。

**代码实现：**

#define MAX 100
    
    #include <cstdio>
    #include <climits>
    #include <algorithm>
    
    using namespace std;
    /* 合并石子问题：环形排列着N堆石子，现在要将石子合并成一堆。
     * 规定如下：每次只能将相邻的两堆石子合并，合并两堆石子所花费的时间为两堆石子的数量和。
     * 求将N堆石子合并成一堆最小花费的时间。（石子分为n堆，石子的数量存储在数组p[0..n-1]中）*/
    
    // 改进版2！！！！！
    int ans[2 * MAX][2 * MAX] = {0};
    int divide[2 * MAX][2 * MAX] = {0};
    
    /* 将环形的石子化为线形 */
    void GetList(int p[], int n) {
        int j = 0;
        for (int i = n; i < 2 * n - 1; i++)
            p[i] = p[j++];
    }
    
    void initDivideArray(int n) {
        for (int i = 0; i < n; i++)
            divide[i][i] = i;
    }
    
    int MergeStone(int p[], int n) {
    
        GetList(p, n);  //化圆为直
        int min_ans = INT_MAX;
        int N = 2 * n - 1;// 线形中石子堆个数看做 2n - 1
        initDivideArray(N);  //初始化divide数组
    
        /* 石子堆的个数：从1到n */
        for (int l = 2; l <= n; l++) {
            /* 讨论l个石子的石子堆 p[i..j] */
            for (int i = 0; i < N - l + 1; i++) {
                int j = i + l - 1;
                /* 计算石子堆p[i..j]的总数 */
                int sum = 0;
                for (int t = i; t <= j; t++)
                    sum += p[t];
    
                /* 依次讨论每一个分割点d:将石子堆p[i..j]分成p[i..k]和 A[k+1..j] */
                ans[i][j] = INT_MAX;
                for (int temp, k = divide[i][j - 1]; k <= divide[i + 1][j]; k++) {
                    temp = ans[i][k] + ans[k + 1][j] + sum;
                    if (temp < ans[i][j]) {
                        ans[i][j] = temp;
                        divide[i][j] = k;
                    }
                }
    
                /* l = n 即我们需要的答案范围，找出最小值 */
                if (l == n) {
                    min_ans = min(ans[i][j], min_ans);
                }
            }
        }
        return min_ans;
    }

--------------------

# 增加一点点难度  —— 同时求最大最小 #

## 石子合并问题 ##

问题描述: 在一个圆形操场的四周摆放着n堆石子. 现在要将石子有次序地合并成一堆. 规定每次只能选相邻的2堆石子合并成一堆, 并将新的一堆石子数记为该次合并的得分. 试设计一个算法, 计算出将n堆石子合并成一堆的最小得分和最大得分.

算法设计: 对于给定n堆石子, 计算合并成一堆的最小得分和最大得分.

数据输入: 第1行是正整数n, 1<=n<=100, 表示有n堆石子. 第2行有n个数, 分别表示n堆石子的个数.

结果输出: 第1行是最小得分, 第2行是最大得分.

<table> 
 <thead> 
  <tr> 
   <th>&nbsp;</th> 
   <th>测试输入</th> 
   <th>期待的输出</th> 
   <th>时间限制</th> 
   <th>内存限制</th> 
   <th>额外进程</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>测试用例 1</td> 
   <td>&nbsp; 
    <ol> 
     <li>36↵</li> 
     <li>53&nbsp;49&nbsp;2&nbsp;9&nbsp;9&nbsp;30&nbsp;2&nbsp;35&nbsp;1&nbsp;46&nbsp;39&nbsp;46&nbsp;42&nbsp;33&nbsp;13&nbsp;41&nbsp;35&nbsp;57&nbsp;38&nbsp;59&nbsp;15&nbsp;40&nbsp;18&nbsp;6&nbsp;46&nbsp;30&nbsp;53&nbsp;31&nbsp;34&nbsp;57&nbsp;41&nbsp;20&nbsp;1&nbsp;42&nbsp;59&nbsp;46&nbsp;45&nbsp;↵</li> 
    </ol></td> 
   <td><a href="http://lexue.bit.edu.cn/mod/programming/testcase/download_io.php?id=139697&amp;test=123257&amp;type=out&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>5913↵</li> 
     <li>24595↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

--------------------

上面我们只讨论了最小的情况，本题需要将最大、最小情况输出。其实最大、最小的套路是一摸一样的，只是在比较的时候改变一下符号而已。且：在求最大的情况下，上面针对求最小时的**四边形不等式的优化不可用**，需要老老实实遍历。

直接附上AC代码：

//
    // Created by A on 2020/3/20.
    //
    #include <cstdio>
    #include <cmath>
    #include <climits>
    #include <algorithm>
    
    #define MAX 300
    
    using namespace std;
    /* 合并石子问题：环形排列着N堆石子，现在要将石子合并成一堆。
     * 规定如下：每次只能将相邻的两堆石子合并，合并两堆石子所花费的时间为两堆石子的数量和。
     * 求将N堆石子合并成一堆最小花费的时间。（石子分为n堆，石子的数量存储在数组p[0..n-1]中）*/
    
    // 改进版2！！！！！
    int min_ans[2 * MAX][2 * MAX] = {0};
    int max_ans[2 * MAX][2 * MAX] = {0};
    int min_divide[2 * MAX][2 * MAX] = {0};
    int max_divide[2 * MAX][2 * MAX] = {0};
    
    
    /* 将环形的石子化为线形 */
    void GetList(int p[], int n) {
        int j = 0;
        for (int i = n; i < 2 * n - 1; i++)
            p[i] = p[j++];
    }
    
    void initDivideArray(int n) {
        for (int i = 0; i < n; i++) {
            min_divide[i][i] = i;
            max_divide[i][i] = i;
        }
    
    }
    
    void MergeStone(int p[], int n) {
    
        GetList(p, n);  //化圆为直
        int N = 2 * n - 1;// 线形中石子堆个数看做 2n - 1
        initDivideArray(N);  //初始化divide数组
    
        /* 石子堆的个数：从1到n */
        for (int l = 2; l <= n; l++) {
            /* 讨论l个石子的石子堆 p[i..j] */
            for (int i = 0; i < N - l + 1; i++) {
                int j = i + l - 1;
                /* 计算石子堆p[i..j]的总数 */
                int sum = 0;
                for (int t = i; t <= j; t++)
                    sum += p[t];
    
                /* 依次讨论每一个分割点d:将石子堆p[i..j]分成p[i..k]和 A[k+1..j] */
                min_ans[i][j] = INT_MAX;
                for (int temp, k = min_divide[i][j - 1]; k <= min_divide[i + 1][j]; k++) {
                    temp = min_ans[i][k] + min_ans[k + 1][j] + sum;
                    if (temp < min_ans[i][j]) {
                        min_ans[i][j] = temp;
                        min_divide[i][j] = k;
                    }
                }
                max_ans[i][j] = INT_MIN;
                for (int temp, k = i; k < j; k++) {
                    temp = max_ans[i][k] + max_ans[k + 1][j] + sum;
                    if (temp > max_ans[i][j]) {
                        max_ans[i][j] = temp;
                        max_divide[i][j] = k;
                    }
                }
            }
        }
    }
    
    int main() {
        int n, p[MAX];
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &p[i]);
    
        MergeStone(p, n);
        int maxResult = INT_MIN, minResult = INT_MAX;
        for (int i = 0, j = n - 1; i < n; i++, j++) {
            maxResult = max(maxResult, max_ans[i][j]);
            minResult = min(minResult, min_ans[i][j]);
        }
        printf("%d\n%d\n", minResult, maxResult);
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2][]

--------------------

**有任何问题欢迎评论交流，如果本文对您有帮助不妨点点赞，嘻嘻~ **

--------------------

# end  #

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 3]

[DP _ 1_ _]: https://blog.csdn.net/weixin_43787043/article/details/104965598
[O_n_3]: https://private.codecogs.com/gif.latex?%5Cbg_white%20O%28n%5E3%29
[bg_white O_n_2]: https://private.codecogs.com/gif.latex?%5Cbg_white%20O%28n%5E2%29
[p_i..j]: https://private.codecogs.com/gif.latex?%5Cinline%20p_%7Bi..j%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20230528/47b5e7d3bb734d25a4daed5e77639b48.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1]: /images/20230528/a33268c517c84a219704fa77407d7cbf.png
[O_n_3 1]: https://private.codecogs.com/gif.latex?%5Cinline%20%5Cbg_white%20O%28n%5E3%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2]: /images/20230528/a07550de6107488ca4acfea42ed66084.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 3]: /images/20230528/40a92a43a47641fb961480c6b73f1aab.png