Codeforces 13C Sequence --DP+离散化

题意：给出一个 n (1 <= n <= 5000)个数的序列 。每个操作可以把 n 个数中的某一个加1 或 减 1。问使这个序列变成非递减的操作数最少是多少 

解法：定义dp[i][j]为将前i个数变为以j为结尾的非递减序列的最少操作次数。

则有： dp[i][j] = min(dp[i][j], min(dp[i][k]) + Cost(原来第i个位置上的数转换到j))  (1 <= k <= j)

即前i个数以j结尾的状态可以由前i-1个数以小于等于j的k结尾的状态转移过来，取一个最小的转移

由于输入过大，需要离散化，将数组的复制b[]排序后用到unique函数，unique函数将数组中相邻元素重复的去掉（实际不去掉，只是放到最后面），然后返回最后一个不与其他元相同的数的地址，所以通过unique(b,b+n)-b可得到该数列实际不同的数有多少个，然后我们上述方程中的j就在这些里面取，Cost其实计算方法为abs(b[j]-a[i])

同时数组不可能存下5000*5000，由于每一个状态都从前一个推来，于是可以用滚动数组。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define lll __int64
using namespace std;
#define N 5007

const lll INF = (1LL<<60);
lll dp[2][N];
lll a[N],b[N];

int main()
{
    int n,i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%I64d",&a[i]);
        b[i] = a[i];
    }
    sort(b,b+n);
    int tot = unique(b,b+n) - b;  //离散化成 0~tot
    for(i=0;i<tot;i++)
    {
        dp[0][i] = abs(b[i]-a[0]);
        dp[1][i] = INF;
    }
    int now = 1;
    for(i=1;i<n;i++)
    {
        lll mini = INF;
        for(j=0;j<tot;j++)
        {
            mini = min(dp[now^1][j],mini);
            dp[now][j] = min(dp[now][j],mini+abs(b[j]-a[i]));
        }
        now = 1-now;
        for(j=0;j<tot;j++)
            dp[now][j] = INF;
    }
    lll mini = INF;
    for(i=0;i<tot;i++)
        mini = min(mini,dp[1-now][i]);
    printf("%I64d
",mini);
    return 0;
}