Skip to content

【动态规划】【区间dp】四边形优化

题目

题目描述

有 N堆石子排成一排，其编号为 1, 2, 3, …, N。

每堆石子有一定的质量，可以用一个整数来描述。现在要将这 NN堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和。合并后，与这两堆石子相邻的石子将和新堆相邻。由于选择的顺序不同，合并的总代价也会不同。

例如有 4堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1，2堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；

如果第二步是先合并 2，3堆，则代价为 77，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入格式

第一行一个整数 N，表示石子的堆数。

第二行 N 个整数，表示每堆石子的质量（均不超过 1000）。

输出格式

输出一个整数，表示最小合并代价。

数据范围

  • 1≤N≤5000

输入样例：

1
2
4
1 3 5 2

输出样例：

1
22

思路

首先可以判断该题为区间dp。对于区间dp问题，子问题可以分解为更小区间的最优解，其朴素算法的通用思路为逐步合并小区间，直到所求区间：

  • 枚举区间长度
  • 枚举区间起点，根据起点和长度计算区间终点
  • 枚举区间起点和终点中分割点取最优

其中，通常使用dp[i][j]进行记录，dp[i][j]的值为合并区间\([i,j]\)的最小花费，最后输出dp[1][num]（其中\(num\)为石子总数）

四边形不等式优化：本题数据范围为5000，如果使用（O(n³)）的朴素思路一定会超时，因此考虑优化。

对于满足以下条件的区间dp可以考虑四边形不等式优化：

  • 设代价函数\(cost(x,y)\)是定义在整数集合上的二元函数。

    对于定义域内的\(a ≤ b ≤ c ≤ d\)，有\(cost(a,c)+cost(b,d)≤cost(a,d)+cost(b,c)\)恒成立。

    注意：此处cost(x,y) 是二元函数（代价函数cost()）的值，即x与y是\(cost（）\)的参数。尽管在石子合并的标准模板中，代价函数的值是这段区间内的代价和\(sum\)，但并不适用于所有能使用四边形不等式优化的情况。

    因此，必须强调此处的\(cost(x,y)\)是以x和y为参数的代价函数的值，而不是代价数组的左右端点。

  • 最优决策点具有单调性。

则有推论：

设p[i][j]为区间[i,j]上的最优决策点。

对于区间[i,j]，设a=p[i][j-1]，b=p[i+1][j]，则区间[i,j]的最优决策点一定在整数集合[a,b]中。

由此可将时间复杂度降低到O(n²)。

Code

 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
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 4005;

int num = 0;
int st[N] = { 0 };      //石子质量
int ist[N] = { 0 };     //前缀和
int dp[N][N] = { 0 }; //dp数组，值为合并区间[i,j]的最小花费 
int p[N][N] = { 0 };       //四边形不等式优化，值为区间[i,j]的最优分割点 

int cost(int i, int j) {
    return ist[j] - ist[i - 1];
}

int main() {
    cin >> num;
    for (int i = 1;i <= num;i++) {
        cin >> st[i];
        ist[i] = ist[i - 1] + st[i];     //前缀和
    }

    memset(dp, INF, sizeof(dp));
    memset(p, INF, sizeof(p));

    for (int i = 1;i <= num;i++) {
        dp[i][i] = 0;
        p[i][i] = i;
    }

    for (int len = 2;len <= num;len++) {
        for (int left = 1;left + len - 1 <= num;left++) {
            int right = left + len - 1;
            p[left][right] = INF;
            for (int k = p[left][right - 1];k <= p[left + 1][right];k++) {
                int c = cost(left, right);
                if (dp[left][k] + dp[k + 1][right] + c < dp[left][right]) {
                    dp[left][right] = dp[left][k] + dp[k + 1][right] + c;
                    p[left][right] = k;
                }
            }
        }
    }
        cout << dp[1][num];

        return 0;
}