题目链接：http://poj.org/problem?id=3666
题意：
题解：
首先要发现上述的引理，可以用数学归纳法证明
假设到k这一位置之前所有的b【1~k-1】都是在a【】中出现过的，那么对于b【k】这一个位置，如果a【k】> b【k-1】，那么b【k】=a【k】时是最优的；如果a【k】< b【k-1】，那么一定存在一个值h，使b【h~k】的值都变为a【k】是最优的，或者b【k】=b【k-1】是最优的，而b【k-1】由假设是在a【】中存在的；对于b【1】这个位置，显然b【1】=a【1】是最优的，由数学归纳法可以得知上述引理成立（打这么多字好累啊啊啊）
这时候我们就可以开始DP了
好题++
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define F(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
const int SIZE=2010;
int n,f[SIZE][SIZE];
int a[SIZE],b[SIZE];
int main()
{scanf("%d",&n);F(i,1,n){scanf("%d",&a[i]);b[i]=a[i];}sort(b+1,b+n+1);int m=unique(b+1,b+n+1)-b-1;memset(f,0x3f,sizeof(f));f[0][0]=0;F(i,1,n){int temp=f[i-1][0];F(j,1,m){temp=min(temp,f[i-1][j]);f[i][j]=temp+abs(a[i]-b[j]);}/* F(i,1,n) F(j,1,m) F(k,0,j)f[i][j]=min(f[i][j],f[i-1][k]+abs(a[i]-b[j]));*/int ans=(1<<30);F(i,1,m) ans=min(ans,f[n][i]);cout<<ans<<endl;return 0;
}