POJ 3666 Making the Grade：動態規劃調整道路高程

題目大意

給定長度 N（≤2000）的道路高程序列 A[i]，需調整為單調非遞增或非遞減序列 B[i]，最小化總成本 Σ|A[i]-B[i]|。輸出最小成本。

關鍵觀察：離散化

最優解中每個 B[i] 必定等於某個原始高程 A[j]（證明：若不等於任何 A[j]，可向最近的 A[j] 移動不增加成本）。因此將所有 A[i] 排序去重作為候選值，問題轉化為：從候選值中選擇 B[i] 使序列單調且成本最小。

DP 定義

• 令 val[1..M] 為排序後的唯一高程值（M ≤ N）。
• dp[i][j]：前 i 個位置，第 i 個位置高程設為 val[j] 時的最小成本。

轉移方程

非遞減情況：

dp[i][j] = min_{k≤j} dp[i-1][k] + |A[i] - val[j]|

非遞增情況：

dp[i][j] = min_{k≥j} dp[i-1][k] + |A[i] - val[j]|

優化：前綴/後綴最小值

計算第 i 行時，維護 minPref[j] = min(minPref[j-1], dp[i-1][j])（非遞減）或 minSuf[j] = min(minSuf[j+1], dp[i-1][j])（非遞增），則轉移變為 O(1)，總時間 O(N*M) = O(N²)。

代碼實現（非遞減 + 非遞增取最小）

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 2005;
const long long INF = 1LL<<60;

int N;
long long A[MAXN], val[MAXN];
long long dp[MAXN];

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &A[i]);
        val[i] = A[i];
    }
    sort(val+1, val+N+1);
    int M = unique(val+1, val+N+1) - val - 1;
    // 非遞減
    for (int j = 1; j <= M; j++) dp[j] = llabs(A[1] - val[j]);
    for (int i = 2; i <= N; i++) {
        long long minPref = INF;
        for (int j = 1; j <= M; j++) {
            minPref = min(minPref, dp[j]);
            dp[j] = minPref + llabs(A[i] - val[j]);
        }
    }
    long long ans = INF;
    for (int j = 1; j <= M; j++) ans = min(ans, dp[j]);
    // 非遞增
    for (int j = 1; j <= M; j++) dp[j] = llabs(A[1] - val[j]);
    for (int i = 2; i <= N; i++) {
        long long minSuf = INF;
        for (int j = M; j >= 1; j--) {
            minSuf = min(minSuf, dp[j]);
            dp[j] = minSuf + llabs(A[i] - val[j]);
        }
    }
    for (int j = 1; j <= M; j++) ans = min(ans, dp[j]);
    printf("%lld\n", ans);
    return 0;
}

複雜度分析

• 時間：O(N log N) 排序 + O(N*M) DP，M≤N，總 O(N²) ≈ 400萬操作，極快。
• 空間：O(N) 滾動數組。

總結

本題是「序列調整為單調」的經典 DP：離散化候選值 + 斜率優化（前綴/後綴最小值）。同類問題包括 POJ 3666、APIO 2014 分裂序列等。關鍵在於證明最優解只取原數組中的值，並利用單調性優化轉移。