POJ 3666 Making the Grade：DP 求單調序列最小修改代價

問題

給定序列 a[1…n]（n ≤ 2000），修改為非嚴格單調（遞增或遞減）序列 b，代價 Σ|a_i−b_i|。求最小代價。

關鍵結論

最優解中每個 b_i 必取自原序列值集合。
離散化排序去重得 v[1…m]。

DP 定義

dp[i][j] = 前 i 個數，第 i 改為 v_j 的最小代價。
遞增情況：dp[i][j] = min_k≤j dp[i−1][k] + |a_i−v_j|。
用滾動數組 + 前綴最小值優化到 O(nm)。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int a[MAXN], b[MAXN], dp[MAXN];
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 0; i < n; ++i) { cin >> a[i]; b[i] = a[i]; }
    sort(b, b+n);
    int m = unique(b, b+n) - b;
    for (int j = 0; j < m; ++j) dp[j] = abs(a[0] - b[j]);
    for (int i = 1; i < n; ++i) {
        int best = dp[0];
        for (int j = 0; j < m; ++j) {
            best = min(best, dp[j]);
            dp[j] = best + abs(a[i] - b[j]);
        }
    }
    int ans = *min_element(dp, dp+m);
    // 遞減情況：對 b 逆序跑同樣 DP，取兩者最小
    reverse(b, b+m);
    for (int j = 0; j < m; ++j) dp[j] = abs(a[0] - b[j]);
    for (int i = 1; i < n; ++i) {
        int best = dp[0];
        for (int j = 0; j < m; ++j) {
            best = min(best, dp[j]);
            dp[j] = best + abs(a[i] - b[j]);
        }
    }
    ans = min(ans, *min_element(dp, dp+m));
    cout << ans << '\n';
    return 0;
}

複雜度

O(n×m) 時間，m ≤ n ≤ 2000，約 400 萬操作；空間 O(m) 滾動數組。