题目大意
给一个数列，长度不超过 5000，每次可以将其中的一个数加 1 或者减 1，问，最少需要多少次操作，才能使得这个数列单调不降
数列中每个数为 -109～109 中的一个数
做法分析
先这样考虑：如果操作的次数最少，那么最终得到的不降的数列，必然是由原始数列中的数组成的，具体的证明可以使用反证法
知道了上面讲述的性质，这题就好搞了
先将原始数列（设为 A，共 n 个数）中所有的数去重并从小到达排序，保存在另一个数列中（设为 B，共 m 个数）
定义状态：f[i][j] 表示将原始数列中的前 i 个数变成单调不降，第 i 个数最多为 B[j] 的最少操作次数
初始化 f[0][0]=abs(A[0]-B[0])， f[0][i]=min{ f[0][i-1], abs(A[0]-B[i]) }
初始化 f[i][0]=f[i-1][0]+abs(A[i]-A[0])，那么有：f[i][j]=min( f[i][j-1], f[i-1][j]+abs(A[i]-B[j]) )
目标状态：f[n-1][m-1]
由于内存的关系，可以使用滚动数组
参考代码
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 #include <algorithm>
5 #include <vector>
6
7 using namespace std;
8
9 typedef long long LL;
10 const int N=5003;
11 const LL INF=(1LL)<<60;
12
13 LL f[2][N], A[N], B[N];
14 vector <int> tub;
15 int n, m;
16
17 int main() {
18 while(scanf("%d", &n)!=EOF) {
19 tub.clear(), m=0;
20 for(int i=0; i<n; i++) {
21 scanf("%I64d", &A[i]);
22 tub.push_back(A[i]);
23 }
24 sort(tub.begin(), tub.end());
25 for(int i=0; i<n; i++) {
26 while(i+1<n && tub[i]==tub[i+1]) i++;
27 B[m++]=tub[i];
28 }
29 memset(f, 0, sizeof f);
30 f[0][0]=abs(A[0]-B[0]);
31 for(int i=1; i<m; i++) f[0][i]=min(f[0][i-1], abs(A[0]-B[i]));
32 for(int i=1; i<n; i++) {
33 int cur=i&1, lst=cur^1;
34 f[cur][0]=f[lst][0]+abs(A[i]-B[0]);
35 for(int j=1; j<m; j++) f[cur][j]=min(f[cur][j-1], f[lst][j]+abs(A[i]-B[j]));
36 }
37 printf("%I64d
", f[(n-1)&1][m-1]);
38 }
39 return 0;
40 }