POJ3666 Making the Grade

发表于 | 分类于 |
字数统计: 383 字

题目大意：给定一个数列，求将这个数列修改为一个单调数列，使得代价最小。

题解

可以证明有一种方案使得新数列中的所有数都来自于老数列，并且代价最小。因此可以把原数列离散化后跑DP，设$f(i, j)$为安排完前$i-1$个数，当前数为$j$（这里的$j$是离散化后的值，即按顺序排列的数列$A$的第$j$个值）时的最小代价。数列递增时，转移方程是

里面那一项可以用一个变量维护最小值，随着$j$的增长而更新。
数列递减时相似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
int n, a[2005], b[2005];
ll f1[2005][2005], f2[2005][2005];
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + n + 1);
    memset(f1, 0x3f, sizeof(f1));
    memset(f2, 0x3f, sizeof(f2));
    for(int i = 1; i <= n; ++i)
        f1[1][i] = f2[1][i] = abs(a[1] - b[i]);
    for(int i = 2; i <= n; ++i){
        ll mini1 = f1[i - 1][1], mini2 = f2[i - 1][n];
        for(int j = 1; j <= n; ++j)
            f1[i][j] = mini1 + 1ll * abs(b[j] - a[i]), mini1 = min(mini1, f1[i - 1][j + 1]);
        for(int j = n; j >= 1; --j)
            f2[i][j] = mini2 + 1ll * abs(b[j] - a[i]), mini2 = min(mini2, f2[i - 1][j + 1]);
    }
    ll ans = f1[0][0];
    for(int i = 1; i <= n; ++i)
        ans = min(ans, min(f1[n][i], f2[n][i]));
    printf("%lld\n", ans);
    return 0;
}