题目：非常多人在一起吃饭。有两组单支的筷子，定义badness为一对筷子长度差的平方，求最小的badness和。

分析：dp，最大公共子序列类似物。

这里利用数学关系找到一个结论：

a < b < c < d 时，（c - a）^2 +（d-b）^2 <（d-a^2）+（c-b）^2；（展开就可以）

所以最优解一定不会交叉，然后先用元素少的串，求长串的LCS的就可以。

权值计算用长度差的平方，而不是1。

这里，能够设置两种状态f（i。j）：

1.以a[i]。b[j]为结束标志的最优解，则 T（n）= n^3    { 须要遍历前一位置，非常多反复 }；

2.a[1..i]与b[1..j]两区间的最优解，则T（n）= n^2   { 仅仅取决本位置选否，去掉反复 }。

说明：（2011-09-24 05:03）。

#include <stdio.h>

#include <stdlib.h>

#define min( a, b ) ((a)<(b)?(a):(b))

int A[ 501 ];

int B[ 501 ];

int T[ 501 ][ 501 ];

int S[ 501 ][ 501 ];

int cmp( const void*a, const void*b )

{

    return *((int *)a) - *((int *)b);

}

int f( int *a, int *b, int N, int M )

{

    for ( int i = 1 ; i <= N ; ++ i )

    for ( int j = i ; j <= M ; ++ j )

        S[ i ][ j ] = (a[ i ]-b[ j ])*(a[ i ]-b[ j ]);

    for ( int i = 1 ; i <= N ; ++ i )

    for ( int j = i ; j <= M ; ++ j )

        T[ i ][ j ] = 0xfffffff;

    for ( int i = 0 ; i <= M ; ++ i )

        T[ 0 ][ i ] = 0;

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

        T[ i ][ i ] = T[ i-1 ][ i-1 ] + S[ i ][ i ];

        for ( int j = i+1 ; j <= M ; ++ j )

            T[ i ][ j ] = min( T[ i-1 ][ j-1 ]+S[ i ][ j ], T[ i ][ j-1 ] );

    }

    return T[ N ][ M ];

}

int main()

{

    int t,N,M,S;

    scanf("%d",&t);

    while ( t -- ) {

        scanf("%d",&N);

        for ( int i = 1 ; i <= N ; ++ i )

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

        scanf("%d",&M);

        for ( int i = 1 ; i <= M ; ++ i )

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

        qsort( &A[ 1 ], N, sizeof( int ), cmp );

        qsort( &B[ 1 ], M, sizeof( int ), cmp );

        if ( N <= M )

            printf("%d\n",f( A, B, N, M ));

        else

            printf("%d\n",f( B, A, M, N ));

    }

    return 0;

}