题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3392

Pie

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 793    Accepted Submission(s): 214

2 3

1.5 2.0

1.5 1.7 2.0

0 0

0.000000

思路：dp+滚动数组

（1）：要求最佳匹配。首先得将两数组从小到大排序~

（2）： 然后再明白dp[][]表示的意思;dp[i][j] 表示a数组中前i个数和b数组中前j个数匹配的最优解

（3）：接下来 看看状态转移方程； if(i==j)dp[i][j]=dp[i-1][j-1]+fabs(a[i]-b[j]);

else dp[i][j]=min(dp[i-1][j-1]+fabs(a[i]-b[i]),dp[i][j-1]);

(4):   由于题目中的n最大取到10000。假设开个数组dp[10000][10000],那么执行不了~那么再观察观察状态转移方程，发现当前这个数是由它左边这列递推过来的。我们能够用一个dp[2][10000]的滚动数组就可以，由于我仅仅关心最后一个dp[n][m]值，所曾经面的一些值被覆盖不影响我后面的求值过程；（能够在纸上画一画，就知道这个滚动数组了）

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <string>

#include <cstdio>

#include <algorithm>

#include <cmath>

const int maxn=11000;

using namespace std;

double a[maxn],b[maxn];

double dp[2][maxn];

int main()

{

 int n,m;

 while(cin>>n>>m)

 {

        if(n==0&&m==0)break;

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

        for(int i=1;i<=m;i++)scanf("%lf",&b[i]);

        double *A=a,*B=b;

        if(n>m){swap(n,m);swap(A,B);}

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

        sort(B+1,B+1+m);

        memset(dp,0,sizeof(dp));

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

         for(int j=i;j<=i+m-n;j++)

         {

          if(i==j)

          {

              dp[i&1][j]=dp[(i-1)&1][j-1]+fabs(A[i]-B[j]);

              //printf("dp[%d][%d] :%.6lf",i,j,dp[i&1][j]);

          }

          else

          {

              dp[i&1][j]=min(dp[(i-1)&1][j-1]+fabs(A[i]-B[j]),dp[i&1][j-1]);

              //printf("dp[%d][%d] :%.6lf",i,j,dp[i&1][j]);

          }

         }

       printf("%.6lf\n",dp[n&1][m]);

 }

 return 0;

}