区间DP | 1：矩阵链乘问题（含优化） —— 例题：矩阵链乘、合并石子

男娘i 2023-07-17 04:34 50阅读 0赞

> **矩阵链乘法问题：** 给定 n 个矩阵的链 <A1, A2, A3, ..., An>，矩阵 Ai 的规模为 ![p\_\{i-1\} \\cdot p\_\{i\} (0\\leq i \\leq n)][p_i-1_ _cdot p_i_ _0_leq i _leq n] 。求完全括号化方案，使得计算乘积A1A2...An所需要标量的乘法次数最少。

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

**目录**

一、算法剖析

1、最优括号化方案的结构特征

2、 一个递归的求解方案

二、算法实现

1、计算最优代价

暂未优化的方法 —— 时间复杂度为 ![O(n^3)][O_n_3]

优化后的方法 —— 时间复杂度降至 ![O(n^2)][O_n_2]

2、构造最优解

三、例题

1、矩阵链乘问题

完整AC代码1：（未优化的时间复杂度 ![O(n^3)][O_n_3] ）

完整AC代码2：（优化的时间复杂度 ![O(n^2)][O_n_2] ）

2、合并石子

完整AC代码1：（未优化的时间复杂度![O(n^3)][O_n_3] ）

完整AC代码2：（优化的时间复杂度 ![O(n^2)][O_n_2] ）

end

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

两个矩阵 A 和 B 只有相容，即 A 的列数等于 B 的行数时，才能相乘。如果 A 是 p×q 矩阵 ，B 是 q×r 矩阵，那么乘积 C 是 p× r 矩阵。计算 C 的进行了 pqr 次乘法运算。我们采用乘法进行的次数来表示**计算的代价**。

对于多个矩阵连乘的问题，我们称作矩阵链乘问题。矩阵的乘法满足结合律，因此任何加括号的方法并不会影响多个矩阵相乘的结果。但**不同的加括号的方案（改变计算顺序）会影响矩阵链乘法计算的代价：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][]

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

# 一、算法剖析 #

### 1、最优括号化方案的结构特征 ###

> 动态规划方法的第一步是寻找最优子结构，然后就可以利用这种子结构，从子问题的最优解构造出原问题的最优解。

（为方便起见，我们用 ![A\_\{i..j \}][A_i..j] 表示![A\_iA\_\{i+1\}...A\_j][A_iA_i_1_...A_j]的乘积结果矩阵）

*  从**整体往局部**看：对于每一个矩阵链 ![A\_\{i..j\}][A_i..j 1]，如果对其括号化，我们应该在某两个矩阵 ![A\_d][A_d] 与 ![A\_\{d+1\}][A_d_1] 之间划分开，然后我们再讨论 ![A\_\{i..d\}][A_i..d] 和![A\_\{d+1..j\}][A_d_1..j]的括号化。
 *  再从**局部往整体**看：计算![A\_\{i..j \}][A_i..j] 的代价 = 计算 ![A\_\{i..d\}][A_i..d] 的代价 + 计算 ![A\_\{d+1..j \}][A_d_1..j 1] 的代价 + 计算 ![A\_\{i..d\} \\cdot A\_\{d+1..j\}][A_i..d_ _cdot A_d_1..j] 的代价。

因此，为了构造一个矩阵链 ![A\_\{i..n \}][A_i..n] 乘法问题的最优解，我们可以将问题分解成两个子问题: ![A\_\{i..d\}][A_i..d] 和 ![A\_\{d+1..n \}][A_d_1..n] 最优化括号问题。求出子问题的最优解后，再将子问题的最优解组合起来。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1][]

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

### 2、 一个递归的求解方案 ###

*  **矩阵的规模**对应存储在一维数组 p\[0..n\] 中，矩阵 ![gif.latex][]![A\_i][A_i] 的规模为 ![p\_\{i-1\}\\cdot p\_\{i\}][p_i-1_cdot p_i]。
 *  **计算的代价**对应储存在二维数组 ans\[1..n, 1..n\] 中，我们用 ans\[i, j\] 表示矩阵 ![A\_\{i..j\}][A_i..j 1] 的最小计算代价，那么原问题的最小计算代价最终就在 ans\[1, n\] 内。 
 *  **最优分割点**对应储存在二维数组 divide\[1..n, 1..n\] 中，我们用 divide\[i, j\] 记录最优代价 ans\[i, j\] 对应的最优分割点 d。（此数组在打印最优结构时十分有用）

根据上述最优括号化方案的结构特征，我们可以列出状态转移方程：

*  当 i = j 时： ![\\bg\_white ans\[i, j\] = 0][bg_white ans_i_ j_ _ 0]
 *  当 i < j 时： ![ans\[i, j\] = min\_\{i\\leq k< j\} (ans\[i, k\] +ans\[k+1,j\] + p\_\{i-1\}p\_kp\_j)][ans_i_ j_ _ min_i_leq k_ j_ _ans_i_ k_ _ans_k_1_j_ _ p_i-1_p_kp_j]

*ps：在定义时将 ans数组全部初始化为0。*

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

# 二、算法实现 #

### 1、计算最优代价 ###

从算法剖析中已知，本问题需要**自底向上**的方法：先处理好子矩阵链的最优问题，再总合起来。

那么我们实现时：应该从长度为2的矩阵链开始讨论，然后再在此基础上讨论长度为3的矩阵链...最终讨论长度的n的矩阵链，即得到答案。在某个已确定长度的讨论中，不可以漏去情况，不然会对最优值有影响。

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

### 暂未优化的方法 —— 时间复杂度为 ![O(n^3)][O_n_3] ###

那么我们的循环结构应该是这样：

*  第一层循环：长度 l = 2..n
 *  第二层循环：讨论每个长度为 l 的矩阵链 ![A\_\{i..j\}][A_i..j 1]：i = 1..n - l +1， j = i + l + 1
 *  第三层循环：确定最优分割点 k = i..j-1

/* 计算n元矩阵链p的最优代价
     * 动态规划的每一步结果储存在 ans与 divide中 */
    void MatrixChainOrder(int p[], int n) {
        /* 矩阵链长度为2到n */
        for (int l = 2; l <= n; l++) {
            /* 讨论长度为l的矩阵链A[i..j] */
            for (int i = 1; i <= n - l + 1; i++) {
                int j = i + l - 1;
                ans[i][j] = INT_MAX;
                /* 依次讨论每一个分割点d:将矩阵链A[i..j]分成A[i..d]和 A[d+1..j] */
                for (int temp, d = i; d < j; d++) {
                    temp = ans[i][d] + ans[d + 1][j] + p[i - 1] * p[d] * p[j];
                    /* 记录下矩阵链A[i..j]最小的情况 */
                    if (temp < ans[i][j]) {
                        ans[i][j] = temp;
                        divide[i][j] = d;
                    }
                }
            }
        }
    }

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

### **优化后的方法 —— 时间复杂度降至**![O(n^2)][O_n_2]  ###

> 上面基本方法的三层循环不可避免，但是可大大削减第三层循环的遍历次数，使得时间复杂度降至![O(n^2)][O_n_2] 。根据矩阵链乘问题模型的特点，其动态规划求解可以使用[四边形不等式优化][Link 1]。（链接里有详细的优化原理、时间复杂度的证明过程)

最佳决策点满足如此关系：![divide\[i\]\[j-1\]\\leq divide\[i\]\[j\]\\leq divide\[i+1\]\[j\]][divide_i_j-1_leq divide_i_j_leq divide_i_1_j]，所以我们的第三层循环可以优化为：在特定区间 \[ divide\[ i \]\[ j -1\], divide\[i +1\]\[ j \] \]内遍历，其遍历范围远远小于n。

*ps：要注意边界情况，需要预先将divide的初值准备好。*

/* 计算n元矩阵链p的最优代价
     * 动态规划的每一步结果储存在 ans与 divide中 */
    void MatrixChainOrder(int p[], int n) {
        /* 初始化divide数组 */
        for (int i = 1; i <= n; i++)
            divide[i][i] = i;
        /* 矩阵链长度为2到n */
        for (int l = 2; l <= n; l++) {
            /* 讨论长度为l的矩阵链A[i..j] */
            for (int i = 1; i <= n - l + 1; i++) {
                int j = i + l - 1;
                ans[i][j] = INT_MAX;
                /* 在特定区间内：依次讨论每一个分割点d，将矩阵链A[i..j]分成A[i..d]和 A[d+1..j] */
                for (int temp, d = divide[i][j - 1]; d <= divide[i + 1][j]; d++) {
                    temp = ans[i][d] + ans[d + 1][j] + p[i - 1] * p[d] * p[j];
                    /* 记录下矩阵链A[i..j]最小的情况 */
                    if (temp < ans[i][j]) {
                        ans[i][j] = temp;
                        divide[i][j] = d;
                    }
                }
            }
        }
    }

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

### 2、构造最优解 ###

我们在二维数组 divide\[i, j\] 中已经记录了 ![A\_\{i..j\}][A_i..j 1] 的最优分界点，由于矩阵链的最优划分可以分解为子链的最优划分，故我们可以递归地打印出来。

/* 根据divide数组，输出A[i..j]的最优情况 */
    void PrintDivide(int i, int j) {
        if (i == j)
            printf("A%d", i);
        else {
            int d = divide[i][j];  //找到分界点
            printf("(");
            PrintDivide(i, d);
            PrintDivide(d + 1, j);
            printf(")");
        }
    }

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

# 三、例题 #

## 1、矩阵链乘问题 ##

输入：

共两行

第一行 N （ 1<=N<=100 ），代表矩阵个数。

第二行有 N+1 个数，分别为 A1 、 A2 ...... An+1 （ 1<=Ak<=2000 ）， Ak 和 Ak+1 代表第 k 个矩阵是个 Ak X Ak+1 形的。

输出：

共两行

第一行 M ，为最优代价。注：测试用例中 M 值保证小于 2^31

第二行为最优顺序。如 (A1((A2A3)A4)) ，最外层也加括号。

注意:测试用例已经保证了输出结果唯一,所以没有AAA的情况.

<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>6↵</li> 
     <li>30&nbsp;35&nbsp;15&nbsp;5&nbsp;10&nbsp;20&nbsp;25↵</li> 
    </ol></td> 
   <td>&nbsp; 
    <ol> 
     <li>15125↵</li> 
     <li>((A1(A2A3))((A4A5)A6))↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td> <p>0</p> <p>&nbsp;</p> </td> 
  </tr> 
 </tbody> 
</table>

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

具体方法上面已经详细讲解啦~

主要注意：当矩阵链中矩阵数目为1的输出要加上括号，不然会wa一个。

### **完整AC代码1：**（未优化的![O(n^3)][O_n_3]时间复杂度） ###

//
    // Created by LittleCat on 2020/3/10.
    //
    
    #include <cstdio>
    #include <climits>
    
    using namespace std;
    #define MAX 2010
    
    int ans[MAX][MAX] = {0}; // 保存矩阵链 A[i..j]的最小代价
    int divide[MAX][MAX] = {0};   // 记录最小代价ans[i,j]对应的分割点
    
    /* 计算n元矩阵链p的最优代价
     * 动态规划的每一步结果储存在 ans与 divide中 */
    void MatrixChainOrder(int p[], int n) {
        /* 矩阵链长度为2到n */
        for (int l = 2; l <= n; l++) {
            /* 讨论长度为l的矩阵链A[i..j] */
            for (int i = 1; i <= n - l + 1; i++) {
                int j = i + l - 1;
                ans[i][j] = INT_MAX;
                /* 依次讨论每一个分割点d:将矩阵链A[i..j]分成A[i..d]和 A[d+1..j] */
                for (int temp, d = i; d < j; d++) {
                    temp = ans[i][d] + ans[d + 1][j] + p[i - 1] * p[d] * p[j];
                    /* 记录下矩阵链A[i..j]最小的情况 */
                    if (temp < ans[i][j]) {
                        ans[i][j] = temp;
                        divide[i][j] = d;
                    }
                }
            }
        }
    }
    
    /* 根据divide数组，输出A[i..j]的最优情况 */
    void PrintDivide(int i, int j) {
        if (i == j)
            printf("A%d", i);
        else {
            int d = divide[i][j];  //找到分界点
            printf("(");
            PrintDivide(i, d);
            PrintDivide(d + 1, j);
            printf(")");
        }
    }
    
    int main() {
        int n;
        scanf("%d", &n);
        int p[MAX];
        for (int temp, i = 0; i <= n; i++)
            scanf("%d", &p[i]);
    
        MatrixChainOrder(p, n);
        printf("%d\n", ans[1][n]);
        if (n == 1)
            printf("(A1)");
        else
            PrintDivide(1, n);
        printf("\n");
    }

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

### **完整AC代码2：**（优化的![O(n^2)][O_n_2]时间复杂度）  ###

//
    // Created by LittleCat on 2020/3/10.
    //
    
    #include <cstdio>
    #include <climits>
    
    using namespace std;
    #define MAX 2010
    
    int ans[MAX][MAX] = {0}; // 保存矩阵链 A[i..j]的最小代价
    int divide[MAX][MAX] = {0};   // 记录最小代价ans[i,j]对应的分割点
    
    /* 计算n元矩阵链p的最优代价
     * 动态规划的每一步结果储存在 ans与 divide中 */
    void MatrixChainOrder(int p[], int n) {
        /* 初始化divide数组 */
        for (int i = 1; i <= n; i++)
            divide[i][i] = i;
        /* 矩阵链长度为2到n */
        for (int l = 2; l <= n; l++) {
            /* 讨论长度为l的矩阵链A[i..j] */
            for (int i = 1; i <= n - l + 1; i++) {
                int j = i + l - 1;
                ans[i][j] = INT_MAX;
                /* 在特定区间内：依次讨论每一个分割点d，将矩阵链A[i..j]分成A[i..d]和 A[d+1..j] */
                for (int temp, d = divide[i][j - 1]; d <= divide[i + 1][j]; d++) {
                    temp = ans[i][d] + ans[d + 1][j] + p[i - 1] * p[d] * p[j];
                    /* 记录下矩阵链A[i..j]最小的情况 */
                    if (temp < ans[i][j]) {
                        ans[i][j] = temp;
                        divide[i][j] = d;
                    }
                }
            }
        }
    }
    
    /* 根据divide数组，输出A[i..j]的最优情况 */
    void PrintDivide(int i, int j) {
        if (i == j)
            printf("A%d", i);
        else {
            int d = divide[i][j];  //找到分界点
            printf("(");
            PrintDivide(i, d);
            PrintDivide(d + 1, j);
            printf(")");
        }
    }
    
    int main() {
        int n;
        scanf("%d", &n);
        int p[MAX];
        for (int temp, i = 0; i <= n; i++)
            scanf("%d", &p[i]);
    
        MatrixChainOrder(p, n);
        printf("%d\n", ans[1][n]);
        if (n == 1)
            printf("(A1)");
        else
            PrintDivide(1, n);
        printf("\n");
    }

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

## 2、合并石子 ##

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

下面是一个 n = 4 、p = \{4, 2, 3, 4\} 的例子，最小花费的时间为26。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2][]

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

**此题本质就是一个矩阵链乘问题 —— 在链中选择每相邻两节点合并，直到全部合并完毕为止。合并石子的过程也就是在矩阵链中加括号的过程。**

**此题也是一个具有最优子结构的问题：**

为了构造一堆石子 ![p\_\{0..n-1\}][p_0..n-1] 合并的最优解，我们可以将问题分解成两个子问题: ![\\bg\_white p\_\{i..d\}][bg_white p_i..d] 和 ![p\_\{d+1..n \}][p_d_1..n]的石子合并问题。求出子问题的最优解后，再将子问题的最优解组合起来。

**寻找一个递归的动态求解方案：**

合并的代价对应储存在二维数组 ans\[0..n-1, 0..n-1\] 中，我们用 ans\[i, j\] 表示合并石子堆![p\_\{i..j\}][p_i..j] 的最小计时间代价，那么原问题的最小计算代价最终就在 ans\[1, n\] 内。

状态转移方程：

*  当 i = j 时： ![\\bg\_white ans\[i, j\] = 0][bg_white ans_i_ j_ _ 0]
 *  当 i < j 时： ![ans\[i\]\[j\] = min\_\{i\\leq k< j\}(ans\[i\]\[k\] + ans\[k+1\]\[j\] + \\sum\_\{i\\leq t\\leq j\} p\[t\])][ans_i_j_ _ min_i_leq k_ j_ans_i_k_ _ ans_k_1_j_ _ _sum_i_leq t_leq j_ p_t]

*ps：在定义时将 ans数组全部初始化为 0。*

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

### **完整AC代码1：**（未优化的![O(n^3)][O_n_3]时间复杂度） ###

核心部分是三层循环

*  第一层循环：长度 l = 2..n
 *  第二层循环：讨论每个长度为 l 的石子堆 ![p\_\{i..j\}][p_i..j 1]：i = 1..n - l +1， j = i + l + 1
 *  第三层循环：确定最优分割点 k = i..j-1

可见，此代码的时间复杂度为 ![O(n^3)][O_n_3]

#define N 100
    
    #include <cstdio>
    #include <climits>
    
    /* 合并石子问题：线性排列着N堆石子，现在要将石子合并成一堆。
     * 规定如下：每次只能将相邻的两堆石子合并，合并两堆石子所花费的时间为两堆石子的数量和。
     * 求将N堆石子合并成一堆最小花费的时间。（石子分为n堆，石子的数量存储在数组p[0..n-1]中）*/
    int ans[N][N] = {0};
    
    int MergeStone(int p[], int n) {
    
        /* 石子堆的个数：从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, sum = 0;
                /* 计算p[i..j]的石子总和 */
                for (int t = i; t <= j; t++)
                    sum += p[t];
                ans[i][j] = INT_MAX;
               /* 依次讨论每一个分割点d:将石子堆p[i..j]分成p[i..k]和 A[k+1..j] */
                for (int temp, k = i; k < j; k++) {
                    temp = ans[i][k] + ans[k + 1][j] + sum;
                    if (temp < ans[i][j])
                        ans[i][j] = temp;
                }
            }
        }
        return ans[0][n - 1];
    }

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

### **完整AC代码2：**（优化的![O(n^2)][O_n_2]时间复杂度）  ###

#define N 100
    
    #include <cstdio>
    #include <climits>
    
    /* 合并石子问题：线性排列着N堆石子，现在要将石子合并成一堆。
     * 规定如下：每次只能将相邻的两堆石子合并，合并两堆石子所花费的时间为两堆石子的数量和。
     * 求将N堆石子合并成一堆最小花费的时间。（石子分为n堆，石子的数量存储在数组p[0..n-1]中）*/
    
    //优化版本！！！！
    
    int ans[N][N] = {0};
    int divide[N][N];
    
    int MergeStone(int p[], int n) {
        /* divide数组初始化*/
        for (int i = 0; i < n; i++)
            divide[i][i] = i;
    
        /* 石子堆的个数：从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, sum = 0;
                /* 计算p[i..j]的石子总和 */
                for (int t = i; t <= j; t++)
                    sum += p[t];
                ans[i][j] = INT_MAX;
                /* 依次讨论特定区间内分割点d:将石子堆p[i..j]分成p[i..k]和 A[k+1..j] */
                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;  //更新p[i..j]的石子堆的最优分割位置
                    }
    
                }
            }
        }
        return ans[0][n - 1];
    }

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

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

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

# end  #

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

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

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

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

[p_i-1_ _cdot p_i_ _0_leq i _leq n]: https://private.codecogs.com/gif.latex?p_%7Bi-1%7D%20%5Ccdot%20p_%7Bi%7D%20%280%5Cleq%20i%20%5Cleq%20n%29
[O_n_3]: https://private.codecogs.com/gif.latex?%5Cinline%20%5Cbg_white%20O%28n%5E3%29
[O_n_2]: https://private.codecogs.com/gif.latex?%5Cinline%20O%28n%5E2%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200319142203665.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70
[A_i..j]: https://private.codecogs.com/gif.latex?A_%7Bi..j%20%7D
[A_iA_i_1_...A_j]: https://private.codecogs.com/gif.latex?A_iA_%7Bi&plus;1%7D...A_j
[A_i..j 1]: https://private.codecogs.com/gif.latex?A_%7Bi..j%7D
[A_d]: https://private.codecogs.com/gif.latex?A_d
[A_d_1]: https://private.codecogs.com/gif.latex?A_%7Bd&plus;1%7D
[A_i..d]: https://private.codecogs.com/gif.latex?A_%7Bi..d%7D
[A_d_1..j]: https://private.codecogs.com/gif.latex?A_%7Bd&plus;1..j%7D
[A_d_1..j 1]: https://private.codecogs.com/gif.latex?A_%7Bd&plus;1..j%20%7D
[A_i..d_ _cdot A_d_1..j]: https://private.codecogs.com/gif.latex?A_%7Bi..d%7D%20%5Ccdot%20A_%7Bd&plus;1..j%7D
[A_i..n]: https://private.codecogs.com/gif.latex?A_%7Bi..n%20%7D
[A_d_1..n]: https://private.codecogs.com/gif.latex?A_%7Bd&plus;1..n%20%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200319150236403.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70
[gif.latex]: https://private.codecogs.com/gif.latex?
[A_i]: https://private.codecogs.com/gif.latex?A_i
[p_i-1_cdot p_i]: https://private.codecogs.com/gif.latex?p_%7Bi-1%7D%5Ccdot%20p_%7Bi%7D
[bg_white ans_i_ j_ _ 0]: https://private.codecogs.com/gif.latex?%5Cinline%20%5Cbg_white%20ans%5Bi%2C%20j%5D%20%3D%200
[ans_i_ j_ _ min_i_leq k_ j_ _ans_i_ k_ _ans_k_1_j_ _ p_i-1_p_kp_j]: https://private.codecogs.com/gif.latex?%5Cinline%20%5Cbg_white%20ans%5Bi%2C%20j%5D%20%3D%20min_%7Bi%5Cleq%20k%3C%20j%7D%20%28ans%5Bi%2C%20k%5D%20&plus;ans%5Bk&plus;1%2Cj%5D%20&plus;%20p_%7Bi-1%7Dp_kp_j%29
[Link 1]: https://oi-wiki.org/dp/opt/quadrangle/#2d1d
[divide_i_j-1_leq divide_i_j_leq divide_i_1_j]: https://private.codecogs.com/gif.latex?%5Cinline%20%5Cbg_white%20divide%5Bi%5D%5Bj-1%5D%5Cleq%20divide%5Bi%5D%5Bj%5D%5Cleq%20divide%5Bi&plus;1%5D%5Bj%5D
[p_0..n-1]: https://private.codecogs.com/gif.latex?p_%7B0..n-1%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200320113658674.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70
[bg_white p_i..d]: https://private.codecogs.com/gif.latex?%5Cbg_white%20p_%7Bi..d%7D
[p_d_1..n]: https://private.codecogs.com/gif.latex?p_%7Bd&plus;1..n%20%7D
[p_i..j]: https://private.codecogs.com/gif.latex?p_%7Bi..j%7D
[ans_i_j_ _ min_i_leq k_ j_ans_i_k_ _ ans_k_1_j_ _ _sum_i_leq t_leq j_ p_t]: https://private.codecogs.com/gif.latex?%5Cinline%20%5Cbg_white%20ans%5Bi%5D%5Bj%5D%20%3D%20min_%7Bi%5Cleq%20k%3C%20j%7D%28ans%5Bi%5D%5Bk%5D%20&plus;%20ans%5Bk&plus;1%5D%5Bj%5D%20&plus;%20%5Csum_%7Bi%5Cleq%20t%5Cleq%20j%7D%20p%5Bt%5D%29
[p_i..j 1]: https://private.codecogs.com/gif.latex?%5Cinline%20p_%7Bi..j%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200111020715220.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70