POJ 36666 Making the Grade 简单DP

题意是：

给出n个数，让你用最小的花费将其改成非递增或非递减的

然后花费就是新序列与原序列各个位置的数的差的绝对值的和

然后可以看到有2000个数，数的范围是10亿

仔细观察可以想象到。其实改变序列中的值时，也只需要改成一个出现在原序列中的值即可

也就是说新序列中的数都是在原数列中出现过的。

那么我们可以将原数列离散化。

dp[i][j] 表示将i位置的数改成离散化后第j个数时 前i个数改造成非递减序列时的最小花费

dp[i][j] = min(dp[i - 1][k]) + abs(a[i] - b[j]) 其中k <= j a[i]是原数列中的第i个数，b[j]是离散化排序过的第j个数

然后我们发现min(dp[i - 1][k]) 这个可以用一个数组记录下来

用mi[i][j] 表示到第i个数时改成离散化第j个数时 所有dp[i][k] (k<=j) 的最小值

mx[i][j] = min(mx[i][j - 1], dp[i][j])

然后

题目还说是可以非递增

那么直接把数列倒过来，不就还是求非递减了么

#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <map>#include <vector>#define MAXN 2222#define INF 1000000007using namespace std;int n, m, ans;int a[MAXN], b[MAXN], dp[MAXN][MAXN], mi[MAXN][MAXN];void gao(int a[]){    memset(dp, 0, sizeof(dp));    memset(mi, 0x3f, sizeof(mi));    for(int i = 0; i < m; i++) mi[0][i] = 0;    for(int i = 1; i < n; i++)        for(int j = 0; j < m; j++)        {            dp[i][j] = mi[i - 1][j] + abs(a[i] - b[j]);            if(j > 0) mi[i][j] = mi[i][j - 1];            mi[i][j] = min(mi[i][j], dp[i][j]);        }    int res = INF;    for(int i = 0; i < m; i++) res = min(res, dp[n - 1][i]);    ans = min(ans, res);}int main(){    scanf("%d", &n);    for(int i = 0; i < n; i++)    {        scanf("%d", &a[i]);        b[i] = a[i];    }    sort(b, b + n);    m = unique(b, b + n) - b;    ans = INF;    gao(a);    reverse(a, a + n);    gao(a);    printf("%d\n", ans);    return 0;}