题目大意
给出了一列数，要求通过修改某些值，使得最终这列数变成有序的序列，非增或者非减的，求最小的修改量。
分析
首先我们会发现，最终修改后，或者和前一个数字一样，或者和后一个数字一样，这样才能修改量最小。
我们先根据原数列排序，确定元素的大小关系，对应编号为p[i]
dp[i][j] 表示考虑前i个元素，最后元素为序列中 第j小元素的最优解
dp[i][j] = MIN(dp[i-1][k]) + abs(a[i]-a[p[j]]), (0<k<=j)
刚开始以为是o(n^3）的复杂度，后来想想，k值在每次j循环的时候就能确定最小值
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define INF 100000000000000
#define maxn 2005
using namespace std;
int n;
typedef long long LL;
LL a[maxn],b[maxn];
LL dp[maxn][maxn];
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=; i<=n; i++)
{
scanf("%I64d",&a[i]);
b[i]=a[i];
}
sort(b+,b++n);
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
dp[i][j]=INF;
for(int j=; j<=n; j++)
{
dp[][j]=(a[]-b[j]);
if(dp[][j]<)
dp[][j]=-dp[][j];
} for(int i=; i<=n; i++)
{
LL k=dp[i-][];
for(int j=; j<=n; j++)
{
k=min(dp[i-][j],k);
LL tem=(a[i]-b[j]);
if(tem<)
tem=-tem;
dp[i][j]=min(dp[i][j],k+tem);
// printf("==%I64d\n",dp[i][j]);
}
}
LL minn=INF;
for(int i=; i<=n; i++)
minn=min(minn,dp[n][i]);
printf("%I64d\n",minn);
}
return ;
}