题意：给出一个 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\n",mini); return 0; }
Codeforces 13C Sequence --DP+离散化,布布扣,bubuko.com
Codeforces 13C Sequence --DP+离散化
原文：http://www.cnblogs.com/whatbeg/p/3866391.html
