题目链接
Dancing Cows SPOJ - DCOWS
It’s the spring dance and, in a rare occurrence, the N (1 ≤ N ≤ 5000) bulls have been invited to dance with the M (N < M ≤ 5000) cows (as long as they stay on their very best behavior).
Farmer John, almost obsessive-compulsive in his organization of dances, wants the spectacle to be as visually attractive as possible. Thus, he wants to pair up the N bulls with cow partners such that the total of all the magnitudes of differences in height is minimized. Bulls have heights B_i (1 ≤ B_i ≤ 1,000,000) and cows have height C_i (1 ≤ C_i ≤ 1,000,000). Of course, some cows will be unmatched since N-M of them will have no partners; ignore their heights.
INPUT FORMAT:
- Line 1: Two space-separated integers: N and M.
- Lines 2..N+1: Line i+1 contains a single integer: B_i.
Lines N+2..M+N+1: Line i+N+1 contains a single integer: C_i.
OUTPUT FORMAT:Line 1: A single integer that is the minimum of the sum of the absolute value of the height differences that can be achieved.
SAMPLE INPUT :
5 7
10
16
12
10
13
7
17
12
10
9
6
11
SAMPLE OUTPUT :
4
INPUT DETAILS:
Five bulls + seven cows with various heights:
Bulls: 10 10 12 13 16
Cows: 6 7 9 10 11 12 17
OUTPUT DETAILS :
Here is one way to achieve a total difference of 4:
Bulls: 10 10 12 13 16
Cows: 6 7 9 10 11 12 17
题意：n只公牛，m只母牛，使公牛和母牛完成匹配，使得匹配的母牛和公牛其差值的绝对值之和最小
思路：dfs暴力匹配
code:
样例
5 7
10 10 12 13 16
6 7 9 10 11 12 17 b: 0 c: 0
b: 1 c: 1
b: 2 c: 2
b: 3 c: 3
b: 4 c: 4
b: 5 c: 5
0 16 11 5
b: 4 c: 5
b: 5 c: 6
0 16 12 4
b: 4 c: 6
b: 5 c: 7
0 16 17 1
b: 4 c: 7
b: 4 c: 7
*
b: 4 c: 6
*
b: 4 c: 5
*
1 13 10 3
b: 3 c: 4
b: 4 c: 5
1 13 11 2
b: 3 c: 5
b: 4 c: 6
1 13 12 1
b: 3 c: 6
b: 4 c: 7
1061109567 13 17 4
b: 3 c: 7
b: 3 c: 7
*
b: 3 c: 6
*
b: 3 c: 5
*
b: 3 c: 4
*
2 12 9 3
b: 2 c: 3
b: 3 c: 4
2 12 10 2
b: 2 c: 4
b: 3 c: 5
2 12 11 1
b: 2 c: 5
b: 3 c: 6
1061109567 12 12 0
b: 2 c: 6
b: 3 c: 7
1061109567 12 17 5
b: 2 c: 7
b: 2 c: 7
*
b: 2 c: 6
*
b: 2 c: 5
*
b: 2 c: 4
*
b: 2 c: 3
*
3 10 7 3
b: 1 c: 2
b: 2 c: 3
3 10 9 1
b: 1 c: 3
b: 2 c: 4
3 10 10 0
b: 1 c: 4
b: 2 c: 5
1061109567 10 11 1
b: 1 c: 5
b: 2 c: 6
1061109567 10 12 2
b: 1 c: 6
b: 2 c: 7
1061109567 10 17 7
b: 1 c: 7
b: 1 c: 7
*
b: 1 c: 6
*
b: 1 c: 5
*
b: 1 c: 4
*
b: 1 c: 3
*
b: 1 c: 2
*
3 10 6 4
b: 0 c: 1
b: 1 c: 2
3 10 7 3
b: 0 c: 2
b: 1 c: 3
3 10 9 1
b: 0 c: 3
b: 1 c: 4
1061109567 10 10 0
b: 0 c: 4
b: 1 c: 5
1061109567 10 11 1
b: 0 c: 5
b: 1 c: 6
1061109567 10 12 2
b: 0 c: 6
b: 1 c: 7
1061109567 10 17 7
b: 0 c: 7
b: 0 c: 7
*
b: 0 c: 6
*
b: 0 c: 5
*
b: 0 c: 4
*
b: 0 c: 3
*
b: 0 c: 2
*
b: 0 c: 1
*
4
理解代码
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<bits/stdc++.h>
using namespace std;
const int maxn = 6000;
const int inf = 0x3f3f3f3f;
long long dp[maxn][maxn];
long long bi[maxn],ci[maxn];
long long n,m;
long long cal(int b,int c)
{
printf("b: %d c: %d\n",b,c);
if(b==n)
return 0;
if(c==m)
return inf;
if(dp[b][c]!=-1)
return dp[b][c];
long long ret = cal(b+1,c+1);
printf("%lld %lld %lld %lld\n",ret,bi[b],ci[c],abs(bi[b]-ci[c]));
ret +=abs(bi[b]-ci[c]);
long long temp = cal(b,c+1);
ret = min(ret,temp);
cout<<endl;
return dp[b][c] = ret;
}
int main()
{
memset(dp,-1,sizeof(dp));
scanf("%lld%lld",&n,&m);
for(int i=0;i<n;i++)
scanf("%lld",&bi[i]);
for(int i=0;i<m;i++)
{
scanf("%d",&ci[i]);
}
sort(bi,bi+n);
sort(ci,ci+m);
printf("%lld\n",cal(0,0));
}
code2(AC): 不要额外开很大的空间，会导致超时
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5010;
const long long inf = 1e17;
long long dp[maxn][maxn];
long long bi[maxn],ci[maxn];
long long n,m;
long long cal(int b,int c)
{
//printf("b: %d c: %d\n",b,c);
if(b==n)
return 0;
if(c==m)
return inf;
if(dp[b][c]!=-1)
return dp[b][c];
long long ret = cal(b+1,c+1)+abs(bi[b]-ci[c]);
// printf("%lld %lld %lld %lld\n",ret,bi[b],ci[c],abs(bi[b]-ci[c]));
//long long temp = cal(b,c+1);
ret = min(ret,cal(b,c+1));
// cout<<endl;
return dp[b][c] = ret;
}
int main()
{
memset(dp,-1,sizeof(dp));
scanf("%lld%lld",&n,&m);
for(int i=0;i<n;i++)
scanf("%lld",&bi[i]);
for(int i=0;i<m;i++)
{
scanf("%lld",&ci[i]);
}
sort(bi,bi+n);
sort(ci,ci+m);
printf("%lld\n",cal(0,0));
}
dp:
#include<bits/stdc++.h>
using namespace std;
long long dp[5001][5001],sel;
const long long maxn = 1e16;
int main()
{
int n,m;
scanf("%d %d",&n,&m);
int bulls[5001]= {0},cows[5001]= {0};
for(int i=1; i<=n; i++)
scanf("%d",&bulls[i]);
for(int i=1; i<=m; i++)
scanf("%d",&cows[i]);
sort(bulls,bulls+n+1);
sort(cows,cows+m+1);
for(int i=0; i<=m; i++)
dp[0][i]=0;
for(int i=1; i<=n; i++)
dp[i][0]=maxn;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
dp[i][j]=min(dp[i][j-1],dp[i-1][j-1]+abs(bulls[i]-cows[j]));
}
}
printf("%lld\n",dp[n][m]);
return 0;
}
京公网安备 11010502036488号