 /**//*
題意:給出A序列,B序列,求最多的匹配,且使總|Ai-Bj|最小
跟中大的5-4一樣
排序之后的匹配是不存在交叉線的,然后DP
dp[i,j] = min(dp[i-1,j-1]+fabs(A[i]-B[j]),dp[i,j-1]) i>j
dp[i-1,j-1]+fabs(A[i]-B[j]) i=j
初始時(shí)dp[0,j] = 0

不過要注意的是:
題目里有說男女的人數(shù)相差不到100,所以我們可以知道一個(gè)人的的可選匹配數(shù)量最多是100個(gè)。
我們就可以用O(n * 100) = O(1000000)的DP來解決這個(gè)問題。相關(guān)的實(shí)現(xiàn)要用到滾存。
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;

const int MAXN = 10005;
const double DINF = 1e100;

 inline double min(double a,double b) {return a<b?a:b;}
 inline int min(int a,int b) {return a<b?a:b;}

double mem[2][MAXN];
double dp[2][MAXN];

int main()
  {
int N,M;
while(scanf("%d%d",&N,&M),N||M)
 {
double *A = mem[0],*B = mem[1];
for(int i=1;i<=N;i++)scanf("%lf",&A[i]);
for(int i=1;i<=M;i++)scanf("%lf",&B[i]);
sort(A+1,A+1+N);
sort(B+1,B+1+M);
 if(N>M) {swap(A,B),swap(N,M);}
for(int j=0;j<=M;j++)dp[0][j]=0;//
 for(int i=1;i<=N;i++) {
dp[i&1][i]=dp[(i-1)&1][i-1]+fabs(A[i]-B[i]);//[i,i] 一定要匹配
for(int j=i+1;j<=min(i+100,M);j++)//題目說 if |n – m| > 100 就沒必要,所以每個(gè)人最多跟100個(gè)人匹配
dp[i&1][j] = min(dp[i&1][j-1],dp[(i-1)&1][j-1]+fabs(A[i]-B[j]));
}
printf("%.6f\n",dp[N&1][M]);
}
return 0;
}

|