再探石子合并问题

解题思路：

本题就是一个经典的区间 $dp$，但是区间 $dp$ 的时间复杂度是 $O(n^3)$，显然这里的数据范围并不支持这么大的复杂度。因此我们要考虑优化。

首先得出区间 $dp$ 的状态转移方程：

$$f_{i,j} = min_{i \leq k < j} \lbrace f_{i,k} + f_{k+1,j} + w(i, j) \rbrace$$

首先 $f_{i,i}=w(i,i)=0$，并且对于 $a \leq b \leq c \leq d$，显然存在 $w(a,d) \geq w(b,c)$，所有条件满足，则 $f$ 满足二维四边形不等式，因此可以用二维四边形不等式优化。

二维四边形不等式优化实现起来非常简单，设 $p_{i,j}$ 表示 $f_{i,j}$ 的最优决策，则对于 $f_{i,j}$，第三层循环改成从 $p_{i,j-1}$ 枚举到 $p_{i+1,j}$ 即可。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 5010, INF = 0x3f3f3f3f;

int n;
int s[N]; //s[i] 表示前 i 个石子堆的质量和
int f[N][N]; //设 f[i][j] 表示将 i ~ j 合并的最小代价
int p[N][N]; //设 p[i][j] 表示 f[i][j] 的最优决策

int main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &s[i]);
        s[i] += s[i - 1];
    }

    //二维四边形不等式优化 dp
    for(int i = 1; i <= n; i++) p[i][i] = i; //初始化决策
    for(int len = 2; len <= n; len++)
        for(int i = 1; i + len - 1 <= n; i++)
        {
            int j = i + len - 1;
            f[i][j] = INF; //初始化状态
            for(int k = p[i][j - 1]; k <= p[i + 1][j]; k++)
            {
                int t = f[i][k] + f[k + 1][j] + s[j] - s[i - 1];
                if(f[i][j] > t) //更新决策
                {
                    f[i][j] = t;
                    p[i][j] = k;
                }
            }
        }
    printf("%d\n", f[1][n]);

    return 0;
}