 /**//*
题意:给出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
初始时dp[0,j] = 0

不过要注意的是:
题目里有说男女的人数相差不到100,所以我们可以知道一个人的的可选匹配数量最多是100个。
我们就可以用O(n * 100) = O(1000000)的DP来解决这个问题。相关的实现要用到滚存。
*/
#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 就没必要,所以每个人最多跟100个人匹配
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;
}

|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|