「洛谷 P5154」数列游戏 - 区间 DP + 线性 DP

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

有一次，HKE 和 LJC 在玩一个游戏。

游戏的规则是这样的：LJC 在纸上写下两个长度均为 \(n\) 的数列 \(a\) 和 \(b\)，两个数列一一对应。HKE 每次可以找两个相邻的数 \(a_i\) 和 \(a_{i + 1}\)，如果它们两个不互质，HKE 可以选择得到 \((b_i + b_{i + 1})\) 分，然后擦掉 \(a\) 和 \(b\) 位置上的第 \(i, i + 1\) 个数，并把两个序列重新按顺序编号。当所有相邻的数互质时，游戏结束。

HKE 想知道他最大得分是多少。

解题思路

对于这道题，我们首先可以使用区间 DP 解决。

我们可以设 \(f_{l, r}\) 表示区间 \([l, r]\) 可合并为 \(1\) 个数所得分数。显然有下列方程：

\[ f_{l, r} = \max\begin{cases} f_{l + 1, r - 1} + b_l + b_r & \gcd(a_l, a_r) \ne 1 \\ f_{l, k} + f_{k + 1, r} & k \in (l, r) \end{cases} \]

初始化：当 \(\gcd(a_i, a_{i + 1}) \ne 1\) 时，\(f_{i, i + 1} = b_i + b_{i + 1}\)，其余情况 \(f_{l, r} = -\infty\)。

接下来我们将利用这个区间 DP 的结果得出正确答案。

接下来我们进行线性 DP。以求出可互质情况下的最终答案。

我们设 \(g_i\) 表示遍历到第 \(i\) 个数的最优答案。于是有下列转移方程：

\[ g_i = \max\begin{cases} g_{i - 1} \\ g_j + f_{j + 1, i} & j \in [0, i) \end{cases} \]

最终答案为 \(g_n\)。

代码演示

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 <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 800;

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int n;
    static long long a[MAXN + 1], b[MAXN + 1];

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%lld", &b[i]);

    static long long f[MAXN + 1][MAXN + 1];
    memset(f, 0xcf, sizeof(f));
    for (int i = 1; i <= n - 1; i++) {
        if (gcd(a[i], a[i + 1]) != 1) {
            f[i][i + 1] = b[i] + b[i + 1];
        }
    }

    for (int len = 4; len <= n; len += 2) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            if (gcd(a[l], a[r]) != 1) f[l][r] = f[l + 1][r - 1] + b[l] + b[r];
            for (int k = l + 1; k <= r - 1; k += 2) f[l][r] = std::max(f[l][r], f[l][k] + f[k + 1][r]);
        }
    }

    static long long g[MAXN + 1];
    for (int i = 2; i <= n; i++) {
        g[i] = g[i - 1];
        for (int j = 0; j <= i - 1; j++) g[i] = std::max(g[i], g[j] + f[j + 1][i]);
    }

    printf("%lld\n", g[n]);

    return 0;
}