再探石子合并

解题思路：

前置知识：四边形不等式问题详解

石子合并问题的升级版。

设 $f[i]$ 表示 $[l \sim r]$ 合并的最小代价

状态转移方程：$f[l][r] = min_{l \leq k < r} \lbrace f[l][k] + f[k + 1][r] \rbrace + \sum_{i-l}^{r} A_i$

$\sum_{i=l}^{r} A_i$ 是区间和，显然满足四边形不等式，且取到等号。

按照二维四边形不等式的解法，设 $p[l][r]$ 表示 $f[l][r]$ 的最优决策，对于 $f[l][r]$，枚举 $k \in [p[l][r - 1], p[l + 1][r]]$，求出 $f[l][r]$ 和 $p[l][r]$，时间复杂度为 $O(N^2)$，能过。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 5010;

int n;
int a[N]; //记录每个石子的质量
int s[N]; //记录 a[] 的前缀和
int f[N][N]; //设 f[i][j] 表示合并 [l ~ r] 的石子需要的最小的代价
int p[N][N]; //设 p[i][j] 表示 f[i][j] 是从哪个决策点转移过来的

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

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

    //初始化
    memset(f, 0x3f, sizeof f);
    for(int i = 1; i <= n; i++)
    {
        f[i][i] = 0;
        p[i][i] = i;
    }

    //二维四边形不等式优化区间 dp
    for(int l = n - 1; l >= 1; l--) //枚举左端点
        for(int r = l + 1; r <= n; r++) //枚举右端点
            for(int k = p[l][r - 1]; k <= p[l + 1][r]; k++) //枚举决策点
                if(l <= k && k < r && f[l][k] + f[k + 1][r] + s[r] - s[l - 1] < f[l][r]) //如果决策点合法且更优
                {
                    f[l][r] = f[l][k] + f[k + 1][r] + s[r] - s[l - 1]; //状态转移方程
                    p[l][r] = k; //记录转移过来的决策点
                }
    printf("%d\n", f[1][n]);

    return 0;
}