路面修整 (grading. cpp/c/pas)

题目描述

FJ 打算好好修一下农场中某条凹凸不平的土路. 按奶牛们的要求, 修好后的路面高度应当单调上升或单调下降, 也就是说, 高度上升与高度下降的路段不能同时出现在修好的路中. 整条路被分成了 N 段, N 个整数 \(A_1, ... , A_N (1 \leq N \leq 2000)\) 依次描述了每一段 路的高度 \((0 \leq A_i \leq 10^9)\). FJ 希望找到一个恰好含 N 个元素的不上升或不下降序列 \(B_1, ... , B_N\), 作为修过的路中每个路段的高度. 由于将每一段路垫高或挖低一个 单位的花费相同, 修路的总支出可以表示为:\(|A_1 - B_1| + |A_2 - B_2| + ... + |A_N - B_N|\)

请你计算一下, FJ 在这项工程上的最小支出是多少. FJ 向你保证, 这个支出不会超过 \(2^{31}-1\).

输入格式

第 1 行: 输入 1 个整数:\(N\)

第 2...... N+1 行: 第 i+1 行为 1 个整数:\(A_i\)

输出格式

第 1 行: 输出 1 个正整数, 表示 FJ 把路修成高度不上升或高度不下降的最小花费

样例输入

7
1
3
2
4
5
3
9

样例输出

3

样例解释

FJ 将第一个高度为 3 的路段的高度减少为 2, 将第二个高度为 3 的路段的高度增加到 5, 总花费为|2-3|+|5-3|=3, 并且各路段的高度为一个不下降序列 1, 2, 2, 4, 5, 5, 9.

Explanation

首先将一条道路的高度改到一个从未出现过的高度毫无意义 (还不如改到已知值)

所以直接用 DP 解就可以了.

甚至不用上优化~

如果 N 的范围变成 200000, 是不是需要优化呢 (雾)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 2010;
const lli infinit = 0x007f7f7f7f7f7f7fll;

int n;
lli a[maxn], b[maxn], dp[maxn][maxn], res;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        b[i] = a[i]; // b[...] is a permutation of a[...].
    }
    // Calculate non-decrease sequence / increasing
    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; i++) {
        dp[i][0] = infinit;
        // It makes no sense to use another value other than the ones given
        // in the sequence a[...] or b[...], as it would be verbose.
        for (int j = 1; j <= n; j++)
            dp[i][j] = min(dp[i][j - 1], dp[i - 1][j] + abs(b[j] - a[i]));
    }
    res = dp[n][n];
    // Calculate non-increase sequence / decreasing
    for (int i = 1; i <= n; i++) {
        dp[i][n + 1] = infinit;
        for (int j = n; j >= 1; j--)
            dp[i][j] = min(dp[i][j + 1], dp[i - 1][j] + abs(b[j] - a[i]));
    }
    res = min(res, dp[n][1]);
    printf("%lld\n", res);
    return 0;
}