读题堪忧啊，敲完了才发现理解错了。。理解题必须看样例啊！！

---

题目链接：

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=110495#problem/S

题意：

给定序列，做出最少的改变，使得新的序列单调非增或者或单调非减。

分析：

先考虑单调非增。

如果后一个元素比前一个小，那么最少改变的情况就是让他和前一个元素相等。如果比前一个元素大或者相等，则不需做出改变。

仔细想想就可以发现其实最后的序列就是由原始数组的元素组成。

那么我们先对原始数组排个序，

设dp[i][j]为考虑第i个位置，放排序后的第j个元素的改变量。

最初按照二维想的，然后直接压缩成一维的。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define sa(a) scanf("%d", &a)

#define sal(a) scanf("%I64d", &a)

const int maxn = 2000 + 5, INF = 0x3f3f3f3f;

int a[maxn], na[maxn];

long long dp[maxn];

int main (void)

{

   int n;sa(n);

   for(int i = 0; i < n; i++) {

        sa(a[i]);na[i] = a[i];}

   sort(na, na + n);

   memset(dp, 0x3f, sizeof(dp));

   for(int i = 0; i < n; i++){

     for(int j = 0; j < n; j++){

        dp[j] = min(dp[j], dp[j - 1] + abs(a[j] - na[i]));

      }

   }

   long long  ans = dp[n - 1];

   memset(dp, 0x3f, sizeof(dp));

   for(int i = n - 1; i >= 0; i--){

     for(int j = 0; j < n; j++){

        dp[j] = min(dp[j], dp[j - 1] + abs(a[j] - na[i]));

      }

   }

   printf("%I64d\n",min(ans, dp[n - 1]));

   return 0;

}