题目链接：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;
}