题目：

dp方程可以是 d [ i ] [ j ] = min ( d [ i - 1 ] [ k ] ) + abs ( a [ i ] - j )，表示a数组前 i 个与结尾为 j 的 b 数组匹配的最优解。0<=k<=j。

可以证明 b 数组中的数都在 a 数组中出现过。详见《算法竞赛进阶指南》。

所以 j 可以表示a [ j ]。当然为了满足不降或不升，需要复制下a数组再排个序来用。

n^2是 LICS 的套路。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const long long INF=0x7fffffff;int n;long long a[2005],b[2005],d[2005][2005],ans=INF;bool cmp(long long x,long long y){    return x>y;}long long as(long long k){    return k<0?-k:k;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)        scanf("%d",&a[i]);    memcpy(b,a,sizeof a);    sort(b+1,b+n+1);    for(int i=1;i<=n;i++)    {        int k=1;//        printf("i=%d\n",i);        for(int j=1;j<=n;j++)        {//            printf(" j=%lld ",b[j]);            k=d[i-1][j]