Poj 3666: Making the Grade

poj3666.md

Poj 3666: Making the Grade

題目

分析

個人認為，這是非典型的題目，想得到的人真強啊。

觀察範測：

1 3 2 4 5 3 9
_ _ x _ _ x _

_ : LIS
x : not in LIS

將 2 增為 3，將 3 增為 5，即可讓序列形成單調

---

到底要將那些不在 LIS 裡的數增加或減少多少（變為哪個數）呢？不知道，所以每個都試試看。

於是得到以下 dp

定義

S[] = 將 A 由小排到大

dp[i][j] = 使序列前 i+1 項變為單調，且將 A[i] 變為「第 j 小的數（S[j]）」的最小成本

答案 *min_element(dp[N-1], dp[N-1] + N)

###轉移方程式

dp[i][j] = min(dp[i - 1][k] | 0 <= k <= j) + abs(S[j] - A[i])

實作

按照定義做，三層迴圈（i, j, k），TLE。

從轉移方程式中可知，min(dp[i-1][k] | 0 <= k <= j) 可以動態維護，降為兩層迴圈（i, j），可 AC。

另外，因只使用到 dp[i-1]，所以可以再使用交互使用 dp 陣列來降低空間複雜度。

其它

得記得 c++98 裡 abs 不能用在 long long 上面。

AC Code

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

using namespace std;

int N;
int A[2000];
int S[2000];
// int dp[2000][2000];
int dp[2][2000];
int *cur = dp[0];
int *pre = dp[1];

int solve() {
    memcpy(S, A, sizeof(A));
    sort(S, S + N);

    for (int j = 0; j < N; j++) {
        // dp[0][j] = abs(S[j] - A[0]);
        cur[j] = abs(S[j] - A[0]);
    }

    swap(cur, pre);

    for (int i = 1; i < N; i++) {
        // O(N^3)
        // for (int j = 0; j < N; j++)
            // dp[i][j] = *min_element(dp[i], dp[i] + j + 1) + abs(S[j] - A[i]);

        // O(N^2)
        // int pre_min_cost = dp[i][0];
        // for (int j = 0; j < N; j++) {
            // pre_min_cost = min(pre_min_cost, dp[i-1][j]);
            // dp[i][j] = pre_min_cost + abs(S[j] - A[i]);
        // }

        // Optimized
        int pre_min_cost = pre[0];
        for (int j = 0; j < N; j++) {
            pre_min_cost = min(pre_min_cost, pre[j]);
            cur[j] = pre_min_cost + abs(S[j] - A[i]);
        }
        swap(cur, pre);
    }

    swap(cur, pre);

    return *min_element(cur, cur + N);
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%d", &A[i]);
    printf("%d\n", solve());
    return 0;
}