「POJ 3666」Making the Grade - 线性 DP

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

题意描述

POJ 链接

给定一个长度为 \(N\) 的序列 \(A\)，要求构造一个长度为 \(N\) 的序列 \(B\)。\(B\) 满足以下条件：

  1. \(B\) 非严格单调（单调递增或单调递减都可），

  2. 在满足 \(1\) 的条件下，使 \(S = \sum_{i = 1}^{N} | A_i - B_i |\)。

仅需求出最小值 \(S\) 即可。题目数据满足 \(1 \leq N \leq 2000\)。

解题思路

首先我们讨论 \(B\) 为非严格单调序列。非严格单调递减同理。两者取最小值即使答案。

构造处理

首先我们提出一个猜想：至少有一种构造方法，满足在 \(S\) 最小的情况下，使 \(B\) 中所有数字均在 \(A\) 中出现过。

这个猜想可以用数学归纳法进行证明：

  1. 显然在 \(N = 1\) 的时候该结论成立。

  2. 设该猜想对于 \(N = x - 1\) 时成立，则对于 \(N = x\)，分为一下情况：

    • \(B_{x - 1} \leq A_x\)，显然 \(B_{x} = A_x\) 的时候 \(S\) 最小。

    • \(B_{x - 1} > A_x\)，可令 \(B_x = B_{x - 1}\)，或者寻找一个值 \(y\)，将 \(B_y, B_{y + 1}, B_{y + 2}, \cdots, B_x\) 赋值为同一个数 \(z\)。令 \(A\) 的中位数为 \(mid\)，若 \(mid < B_{y - 1}\)，则 \(z = B_{y - 1}\)，否则 \(z = mid\)。从中位数性质易得该结论。

动态规划

接下来即可进行动态规划。令排序过的 \(A\) 为 \(S\)，我们可以设数组 \(f_{i, j}\)，其中 \(i\) 表示目标是求 \(B\) 的第 \(i\) 项，\(j\) 表示 \(B_i = S_j\) 的情况。\(f_{i, j}\) 的值表示 \(A\) 在 \(i\) 及之前的序列在使用 \(S\) 在 \(j\) 及以前的序列的数的情况下 \(S\) 的最小值。我们可以推出下列状态转移方程：

\[ f_{i, j} = \min \limits_{1 \leq k \leq j} \{ f_{i - 1, k} + |A_i - S_j| \} \]

初始状态为 \(f = INF\)，目标所求为 \(\min \limits_{1 \leq i \leq n} f_{n, i}\)。

由于状态转移方程中 \(f_{i - 1, k}\) 的最小值滚动时只会受到最后一个数的影响，我们可以将前一个最小值存起来，更新时仅比较前一个最小值和 \(f_{i - 1, k}\)。可以将时间复杂度从 \(O(n^3)\) 优化到 \(O(n^2)\)。

代码演示

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

const int MAXN = 2000, INF = 0x3f3f3f3f;

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

    std::cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    // 对单调递增的处理
    static int fG[MAXN + 1][MAXN + 1], s[MAXN + 1];
    memset(fG, 0x3f, sizeof(fG));
    memcpy(s, a, sizeof(a));
    std::sort(s + 1, s + n + 1);
    for (int i = 1; i <= n; i++) fG[0][i] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            fG[i][0] = std::min(fG[i][0], fG[i - 1][j]);
            fG[i][j] = fG[i][0] + abs(a[i] - s[j]);
        }
    }

    // 对单调递减的处理
    static int fL[MAXN + 1][MAXN + 1];
    memset(fL, 0x3f, sizeof(fG));
    memcpy(s, a, sizeof(a));
    std::sort(s + 1, s + n + 1);
    for (int i = 1; i <= n; i++) fL[0][i] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            fL[i][0] = std::min(fL[i][0], fL[i - 1][j]);
            fL[i][j] = fL[i][0] + abs(a[i] - s[j]);
        }
    }

    int ans = INF;
    for (int i = 1; i <= n; i++) {
        if (fG[n][i] < ans) ans = fG[n][i];
        if (fL[n][i] < ans) ans = fL[n][i];
    }

    std::cout << ans << std::endl;

    return 0;
}