/**//* 题意:给出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
搜索
最新评论
|
|