POJ3666序列最小差值

题目：http://poj.org/problem?id=3666

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<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const long long INF=0x7fffffff;

int n;

long long a[],b[],d[][],ans=INF;

bool cmp(long long x,long long y)

{

    return x>y;

}

long long as(long long k)

{

    return k<?-k:k;

}

int main()

{

    scanf("%d",&n);

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

        scanf("%d",&a[i]);

    memcpy(b,a,sizeof a);

    sort(b+,b+n+);

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

    {

        int k=;

//        printf("i=%d\n",i);

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

        {

//            printf(" j=%lld ",b[j]);

            k=d[i-][j]<d[i-][k]?j:k;

//            printf("k=%lld d[i-1][k]=%lld ",b[k],d[i-1][k]);

            d[i][j]=d[i-][k]+as(a[i]-b[j]);

//            printf("d=%lld\n",d[i][j]);

        }

    }

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

        ans=min(ans,d[n][i]);

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

    memset(d,,sizeof d);

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

    {

        int k=;

//        printf("i=%d\n",i);

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

        {

//            printf(" j=%lld ",b[j]);

            k=d[i-][j]<d[i-][k]?j:k;

//            printf("k=%lld d[i-1][k]=%lld ",b[k],d[i-1][k]);

            d[i][j]=d[i-][k]+as(a[i]-b[j]);

//            printf("d=%lld\n",d[i][j]);

        }

    }

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

        ans=min(ans,d[n][i]);

    printf("%lld",ans);

    return ;

}