Dancing Cows 訓練賽題目--低級比對（暴力） [SPOJ-DCOWS]

題目連結

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:  c: 
b:  c: 
b:  c: 
b:  c: 
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
*

b:  c: 
*

b:  c: 
*

   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
*

b:  c: 
*

b:  c: 
*

b:  c: 
*

   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
*

b:  c: 
*

b:  c: 
*

b:  c: 
*

b:  c: 
*

   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
*

b:  c: 
*

b:  c: 
*

b:  c: 
*

b:  c: 
*

b:  c: 
*

   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
   
b:  c: 
b:  c: 
*

b:  c: 
*

b:  c: 
*

b:  c: 
*

b:  c: 
*

b:  c: 
*

b:  c: 
*


           

了解代碼

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<bits/stdc++.h>
using namespace std;
const int  maxn = ;
const int inf = ;
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 ;
    if(c==m)
        return inf;
    if(dp[b][c]!=-)
        return dp[b][c];
    long long ret = cal(b+,c+);
    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+);
    ret = min(ret,temp);
        cout<<endl;
    return dp[b][c] = ret;

}
int main()
{
    memset(dp,-,sizeof(dp));
    scanf("%lld%lld",&n,&m);
    for(int i=;i<n;i++)
        scanf("%lld",&bi[i]);
    for(int i=;i<m;i++)
    {
        scanf("%d",&ci[i]);
    }
    sort(bi,bi+n);
    sort(ci,ci+m);
    printf("%lld\n",cal(,));

}

           

code2(AC): 不要額外開很大的空間，會導緻逾時

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<bits/stdc++.h>
using namespace std;
const int  maxn = ;
const long long inf = ;
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 ;
    if(c==m)
        return inf;
    if(dp[b][c]!=-)
        return dp[b][c];
    long long ret = cal(b+,c+)+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+));
     //   cout<<endl;
    return dp[b][c] = ret;

}
int main()
{
    memset(dp,-,sizeof(dp));
    scanf("%lld%lld",&n,&m);
    for(int i=;i<n;i++)
        scanf("%lld",&bi[i]);
    for(int i=;i<m;i++)
    {
        scanf("%lld",&ci[i]);
    }
    sort(bi,bi+n);
    sort(ci,ci+m);
    printf("%lld\n",cal(,));

}
           

dp:

#include<bits/stdc++.h>
using namespace std;
long long dp[][],sel;
const long long maxn = ;
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int bulls[]= {},cows[]= {};
    for(int i=; i<=n; i++)
        scanf("%d",&bulls[i]);
    for(int i=; i<=m; i++)
        scanf("%d",&cows[i]);
    sort(bulls,bulls+n+);
    sort(cows,cows+m+);
    for(int i=; i<=m; i++)
        dp[][i]=;
    for(int i=; i<=n; i++)
        dp[i][]=maxn;
    for(int i=; i<=n; i++)
    {
        for(int j=; j<=m; j++)
        {
            dp[i][j]=min(dp[i][j-],dp[i-][j-]+abs(bulls[i]-cows[j]));
        }
    }
    printf("%lld\n",dp[n][m]);
    return ;
}