题意：

思路：

dp[i][j] 表示前i + 1个数变成单调且最后一个数是B[j]，此时的最小成本

dp[i][j] = min(dp[i – 1][k]) + |A[i] – B[j]| 【k = 0->j】

但是我们发现现在的复杂度是O(n^3) 卡不过去

怎么优化呢

保存个最小值不就行了嘛….复杂度O(n^2)

Ps：这道题可以优化空间…

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 2222

int n,a[N],b[N],c[N],f[N][N],ans=0x7fffffff;

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];

    sort(b+1,b+1+n);

    for(int i=1;i<=n;i++)c[i]=lower_bound(b+1,b+1+n,a[i])-b;

    memset(f,0x7f,sizeof(f));

    for(int i=1;i<=n;i++)f[0][i]=0;

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

        int minn=0x7fffffff;

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

            minn=min(minn,f[i-1][j]);

            f[i][j]=minn+abs(b[j]-b[c[i]]);

        }

    }

    for(int i=1;i<=n;i++)ans=min(ans,f[n][i]);

    printf("%d\n",ans);

}

优化空间的版本~

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 2222

int n,a[N],b[N],c[N],f[2][N],ans=0x7fffffff;

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];

    sort(b+1,b+1+n);

    for(int i=1;i<=n;i++)c[i]=lower_bound(b+1,b+1+n,a[i])-b;

    memset(f,0x7f,sizeof(f));

    for(int i=1;i<=n;i++)f[0][i]=0;

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

        int minn=0x7fffffff;

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

            minn=min(minn,f[(i+1)%2][j]);

            f[i%2][j]=minn+abs(b[j]-b[c[i]]);

        }

    }

    for(int i=1;i<=n;i++)ans=min(ans,f[n%2][i]);

    printf("%d\n",ans);

}