Algorithm DP C/C++

AcWing 283-移动服务 多边形

区间DP

Posted by Leo on February 21, 2023

AcWing 283 多边形

题目大意

题目链接见此283. 多边形 - AcWing题库

题解

高级的合并石子问题，需要解决的问题包括

  • 成环
  • 乘法

状态设计仿照合并石子即可，令$f_{i, j, 0}$表示区间$[i,j]$的最大值， $f_{i , j, 1}$表示区间$[i, j]$的最小值，维护最小值的原因下面会说

成环解决

常用套路，在[1, n]之后再补上一段[1, N]。第一步的选边删除策略也可以转变成枚举的全区间结点[1, N], [2, N+1], ……，[N, 2N-1]，从中找到最大值

1
2
3
4
5
6
7
8
9
10

int maxF = -0x7fffffff;
    for (int i = 1; i <= N; i++) {
        maxF = max(maxF, F[i][i + N - 1][0]);
    }
    cout << maxF << endl;
    for (int i = 1; i <= N; i++) {
        if (F[i][i + N - 1][0] == maxF) {
            cout << i << " ";
        }
    }

乘法解决

乘法带来的改变就体现在负数时带来的影响，最小值与最小值的乘积可能变成最大值，因此需要额外维护区间的最小值

以最大值为例，考虑负数带来的影响

  • 左右区间最小值均大于0， $\text{max} \leftarrow \text{max} \times \text{max}$
  • 左右区间最大值均小于0，$\text{max} \leftarrow \text{min} \times \text{min} $
  • 左区间横跨0，右区间均大于0，， $\text{max} \leftarrow \text{max} \times \text{max} $
  • 左区间横跨0，右区间均小于0，$\text{max} \leftarrow \text{min} \times \text{max} $
  • 左区间横跨0，右区间横跨0, $\text{max} \leftarrow \text{max} \times \text{max}$
  • 左区间均大于0，右区间横跨0, $\text{max} \leftarrow \text{max} \times \text{max}$
  • 左区间均大于0，右区间均小于0， $\text{max} \leftarrow \text{max} \times \text{max}$
  • 左区间均小于0，右区间均大于0， $\text{max} \leftarrow \text{max} \times \text{min}$
  • 左区间均小于于0，右区间横跨0， $\text{max} \leftarrow \text{min} \times \text{min}$

合并来说

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

 for (int k = 2; k <= N; k++) { // k表示区间长度
        for (int i = 1; i <= N * 2 - k + 1; i++) { // i区间右端点
            int j = i + k - 1;
            for (int l = i; l < j; l++) {
                if (op[l+1] == 't') {
                    F[i][j][0] = max(F[i][j][0], F[i][l][0] + F[l + 1][j][0]);
                    F[i][j][1] = min(F[i][j][1], F[i][l][1] + F[l + 1][j][1]);
                } else {
                    F[i][j][0] = max(F[i][j][0], F[i][l][0] * F[l + 1][j][0]);
                    F[i][j][0] = max(F[i][j][0], F[i][l][1] * F[l + 1][j][1]);
                    F[i][j][0] = max(F[i][j][0], F[i][l][0] * F[l + 1][j][1]);
                    F[i][j][0] = max(F[i][j][0], F[i][l][1] * F[l + 1][j][0]);
                    F[i][j][1] = min(F[i][j][1], F[i][l][1] * F[l + 1][j][1]);
                    F[i][j][1] = min(F[i][j][1], F[i][l][0] * F[l + 1][j][1]);
                    F[i][j][1] = min(F[i][j][1], F[i][l][1] * F[l + 1][j][0]);
                    F[i][j][1] = min(F[i][j][1], F[i][l][0] * F[l + 1][j][0]);
                }
            }
        }
    }

参考代码

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
62
63
64
65
66
67

//
// Created by Leo on 2023/2/28.
//

#include <bits/stdc++.h>

using namespace std;
// 进阶版合并石子 （环；乘法）
const int MaxN = 60;

// *2 是因为要考虑环的情况, f[n,n,0]max, f[n,n, 1]min 因为有负数和乘法所以也要维护最小
int N, F[MaxN*2][MaxN*2][2], num[MaxN*2];
char op[MaxN*2];

int main() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> op[i] >> num[i];
        op[i + N] = op[i];
        num[i + N] = num[i];
    }
    // initialization
    for (int i = 1; i <= N * 2; i++) {
        F[i][i][0] = num[i];
        F[i][i][1] = num[i];
    }

    for (int i = 1; i <= N * 2; i++)
        for (int j =1; j <= N * 2; ++j) {
            if (i == j) continue;
            F[i][j][0] = -0x3f3f3f3f;
            F[i][j][1] = 0x3f3f3f3f;
        }
    // f(i, j, 0) 表示从i到j的最大值， 区间dp开始
    for (int k = 2; k <= N; k++) { // k表示区间长度
        for (int i = 1; i <= N * 2 - k + 1; i++) { // i区间右端点
            int j = i + k - 1;
            for (int l = i; l < j; l++) {
                if (op[l+1] == 't') {
                    F[i][j][0] = max(F[i][j][0], F[i][l][0] + F[l + 1][j][0]);
                    F[i][j][1] = min(F[i][j][1], F[i][l][1] + F[l + 1][j][1]);
                } else {
                    F[i][j][0] = max(F[i][j][0], F[i][l][0] * F[l + 1][j][0]);
                    F[i][j][0] = max(F[i][j][0], F[i][l][1] * F[l + 1][j][1]);
                    F[i][j][0] = max(F[i][j][0], F[i][l][0] * F[l + 1][j][1]);
                    F[i][j][0] = max(F[i][j][0], F[i][l][1] * F[l + 1][j][0]);
                    F[i][j][1] = min(F[i][j][1], F[i][l][1] * F[l + 1][j][1]);
                    F[i][j][1] = min(F[i][j][1], F[i][l][0] * F[l + 1][j][1]);
                    F[i][j][1] = min(F[i][j][1], F[i][l][1] * F[l + 1][j][0]);
                    F[i][j][1] = min(F[i][j][1], F[i][l][0] * F[l + 1][j][0]);
                }
            }
        }
    }

    int maxF = -0x7fffffff;
    for (int i = 1; i <= N; i++) {
        maxF = max(maxF, F[i][i + N - 1][0]);
    }
    cout << maxF << endl;
    for (int i = 1; i <= N; i++) {
        if (F[i][i + N - 1][0] == maxF) {
            cout << i << " ";
        }
    }
    return 0;
}
CATALOG
    ▲ TOP