跳转至

区间DP

  1. 环形 --> 链形
  2. 方案数
  3. 区间DP+高精度
  4. 二维区间DP

实现方式:

  1. 迭代式: recommended, especially in 1D
    • 1: 枚举长度 for (int Len=1; Len<=n; Len++)
    • 2: 枚举左端点 for (iny L=1; L+Len-1<=n; L++)
    • 右端点: R = L+Len-1
  2. 记忆化搜索

282 石子合并

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

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

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

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

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

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

动态规划

  • 状态表示: f[i][j]
    • 表示将 i 到 j 这一段石子合并成一堆的方案的集合
    • 属性 Min
  • 状态计算:
C++
 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
#include <iostream>
#include <cstring>

using namespace std;

const int N = 307;

int a[N], s[N];
int f[N][N];

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        s[i] += s[i - 1] + a[i];
    }

    // 初始化 (求min, 因此init成MAX)
    memset(f, 0x3f, sizeof f);

    // 区间 DP 枚举套路: 长度+左端点 
    for (int len = 1; len <= n; len ++) 
    {   // len表示[i, j]的元素个数
        for (int i = 1; i + len - 1 <= n; i ++) 
        {
            int j = i + len - 1; // 自动得到右端点

            if (len == 1) {
                f[i][j] = 0;  // 边界初始化
                continue;
            }

            for (int k = i; k <= j - 1; k ++) 
            {   // 必须满足k + 1 <= j
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }

    cout << f[1][n] << endl;
    return 0;
}

1068 环形石子合并

将 “环” 展成 “链” 的方法: n的环 -> 2n的链

将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。

规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 n 及每堆的石子数，并进行如下计算：

  • 选择一种合并石子的方案，使得做 n−1 次合并得分总和最大
  • 选择一种合并石子的方案，使得做 n−1 次合并得分总和最小

输入格式:

  1. 第一行包含整数 n，表示共有 n 堆石子
  2. 第二行包含 n 个整数，分别表示每堆石子的数量

C++
 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
51
52
53
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 410, INF = 0x3f3f3f3f;

int n;
int w[N], s[N];
int f[N][N], g[N][N]; // f: DP求min; g: DP求max

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> w[i];
        w[i + n] = w[i]; // 1~n + 1~n
    }

    // 前缀和预处理, 以求得 sum[i,j]
    for (int i = 1; i <= n * 2; i ++ ) s[i] = s[i - 1] + w[i];

    memset(f, 0x3f, sizeof f);  // 求min, init成MAX
    memset(g, -0x3f, sizeof g); // 求max, init成MIN

    for (int len = 1; len <= n; len ++ )
        for (int l = 1; l + len - 1 <= n * 2; l ++ )
        {
            int r = l + len - 1;
            if (l == r) f[l][r] = g[l][r] = 0;
            else
            {
                for (int k = l; k < r; k ++ )
                {
                    f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                    g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
                }
            }
        }

    int minv = INF, maxv = -INF;
    for (int i = 1; i <= n; i ++ )
    {
        minv = min(minv, f[i][i + n - 1]);
        maxv = max(maxv, g[i][i + n - 1]);
    }

    cout << minv << endl << maxv << endl;

    return 0;
}

320 能量项链

比如:

  • input: 2 3 5 10
  • 珠子: (2,3) (3,5) (5,10) (10,2)
  • 改进: (2,3,5,10,2) 扫描一遍即可

baseline: 动态规划 (线形)

动态规划 (环形)

将 “环” 展成 “链” 的方法: n的环 -> 2n的链

C++
1
f[L, R] = max (f[L, K] + f[K, R] + w[L]*w[K]*w[R])

代码:

C++
 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
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int n;
int w[N];
int f[N][N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> w[i];
        w[i + n] = w[i]; // 1~n + 1~n
    }

    // 3: 最少3才能合并
    // n+1: 回顾上面 2 3 5 10 -> 2 3 5 10 2
    for (int len = 3; len <= n + 1; len ++ ) // 长度
        for (int l = 1; l + len - 1 <= n * 2; l ++ ) // 左端点
        {
            int r = l + len - 1;
            for (int k = l + 1; k < r; k ++ )
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
        }

    int res = 0;
    for (int l = 1; l <= n; l ++ ) res = max(res, f[l][l + n]);

    cout << res << endl;
    return 0;
}

1069 凸多边形的划分

给定一个具有 N 个顶点的凸多边形，将顶点从 1 至 N 标号，每个顶点的权值都是一个正整数

将这个凸多边形划分成 N−2 个互不相交的三角形，对于每个三角形，其三个顶点的权值相乘都可得到一个权值乘积，试求所有三角形的顶点权值乘积之和至少为多少

出发点:

动态规划:

代码:

479 加分二叉树

区间DP 如何记录方案

分析:

动态规划:

需要记录方案, 等价于 存 f[L, R] 是从谁转移过来的. 因此需要开一个g[]数组来存转移

g[L][R]: 存 f[L][R] 的 根节点

C++
 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
51
52
#include <iostream>
using namespace std;

const int N = 31;
int n;
int w[N];
int f[N][N];
int g[N][N]; // g(l, r)用于记录(l, r)区间内的根结点

void dfs(int left, int right) 
{
    if (left > right) return;
    int root = g[left][right];
    //前序遍历，根-左-右
    cout << root << " ";
    dfs(left, root - 1);
    dfs(root + 1, right);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    for (int i = 1; i <= n; ++i) f[i][i] = w[i], g[i][i] = i;
    // 叶结点的权值是本身，这是题目规定的
    // 初始化f和g
    // 当然这个可以写进循环里，特判len==1的情况，我这样写是便于理解

    for (int len = 2; len <= n; ++len) 
    {
        for (int l = 1; l + len - 1 <= n; ++l) 
        {
            int r = l + len - 1;
            for (int k = l; k <= r; ++k) 
            {
                int l_tr = k == l ? 1 : f[l][k - 1];
                int r_tr = k == r ? 1 : f[k + 1][r];
                int score = l_tr * r_tr + w[k];

                if (score > f[l][r]) 
                {
                    f[l][r] = score;
                    g[l][r] = k;
                }
            }
        }
    }

    cout << f[1][n] << endl;
    dfs(1, n);
    return 0;
}

321 棋盘分割

二维区间DP + 记忆化搜索

数学分析: 目标

动态规划:

C++
 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
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 16;
int n, m = 8;
int s[N][N];
double f[N][N][N][N][N];
double X;

double get(int x1, int y1, int x2, int y2)  //求该矩阵的 n\sigma^2
{
    double delta = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
    delta = delta - X;
    return delta * delta;
}

double dp(int k, int x1, int y1, int x2, int y2)
{
    if (f[k][x1][y1][x2][y2] >= 0) return f[k][x1][y1][x2][y2]; // 记忆化搜索
    if (k == n) return f[k][x1][y1][x2][y2] = get(x1, y1, x2, y2);  // 更新初始状态

    double t = 1e9; //初始化为无穷大
    for (int i = x1; i < x2; i ++ ) //横着切
    {
        t = min(t, dp(k + 1, x1, y1, i, y2) + get(i + 1, y1, x2, y2));
        t = min(t, dp(k + 1, i + 1, y1, x2, y2) + get(x1, y1, i, y2));
    }
    for (int i = y1; i < y2; i ++ ) //竖着切
    {
        t = min(t, dp(k + 1, x1, y1, x2, i) + get(x1, i + 1, x2, y2));
        t = min(t, dp(k + 1, x1, i + 1, x2, y2) + get(x1, y1, x2, i));
    }
    return f[k][x1][y1][x2][y2] = t;
}

int main()
{
    //读入
    scanf("%d", &n);
    for (int i = 1; i <= m; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &s[i][j]);

    //预处理前缀和
    for (int i = 1; i <= m; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    //初始化所有状态
    memset(f, -1, sizeof f);
    //计算均值X拔
    X = (double) s[m][m] / n;

    //记忆化搜索
    printf("%.3lf\n", sqrt(dp(1, 1, 1, m, m) / n));
    return 0;
}