题目链接

Making the Grade POJ - 3666

普遍反映这个题POJ的数据水， 所以可以交一下zstu 3698: 单调序列2

思路

$$ \begin{aligned}以不降为例 dp[i][j]表示第i个数为第j大值时的最优解\\\\dp[i][j] = min(dp[i][j - 1], dp[i - 1][j] + w)\\\\w为第i个数变成第j大值所需开销\end{aligned} $$

时间复杂度

$$ O(N^2) $$

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 5000 + 10;

long long dp[2][MAXN];
int a[MAXN], b[MAXN];
int n;

long long gao_in() {
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; i++) {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i & 1][j] = min(dp[i & 1][j - 1], dp[(i - 1) & 1][j] + abs(a[i] - b[j]));
        }
    }
    return dp[n & 1][n];
}


long long gao_de() {
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; i++) {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = n; j >= 1; j--) {
            dp[i & 1][j] = min(dp[i & 1][j + 1], dp[(i - 1) & 1][j] + abs(a[i] - b[j]));
        }
    }
    return dp[n & 1][n];
}

int main() {
    scanf("%d", &n);// don't forget &
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);// don't forget &
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    printf("%lld", min(gao_in(), gao_de()));
    return 0;
}