2

一个 SPOJ 问题：

给定两个数组A和B之间的正1数1,000,000。我必须将每个整数与一个整数配对a，以使差异的绝对值之和最小化。每个最多可以包含 5000 个整数。AbBAB

例如：

让A=[10, 15, 13]和B=[14,13, 12]，那么最好的配对是(10, 12)和因为(15, 14)，这是我们能做到的最少的。因此，达到的最小总和是。(13, 13)|10-12|+|15-14|+|13-13|=33

我相信这是一个动态编程问题。

编辑：

数组可能有不同的大小，但每个最多可以包含 5000 个元素。

我的代码：

#include <cmath>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

static int DP[5002][5002], N, M, tmp;
vector<int> B, C;

int main()
{
    scanf("%d %d", &N, &M); memset(DP, -1, sizeof DP);
    B.push_back(0); C.push_back(0); DP[0][0]=0;
    for(int i=1; i<=N; ++i){scanf("%d", &tmp); B.push_back(tmp);} \\inputting numbers.
    for(int i=1; i<=M; ++i){scanf("%d", &tmp); C.push_back(tmp);}
    sort(B.begin(), B.end()); sort(C.begin(), C.end());         \\Sorting the two arrays.

    if(C.size()<=B.size()){                         \\Deciding whether two swap the order of arrays.
        for(int i=1; i<=N; ++i){
            for(int j=1; j<=M; ++j){
                if(j>i)break;
                if(j==1)DP[i][j]=abs(C[j]-B[i]);
                else{
                    tmp=DP[i-1][j-1]+abs(C[j]-B[i]);
                    DP[i][j]=(DP[i-1][j]!=-1)? min(tmp, DP[i-1][j]): tmp;
                }
            }
        }
        printf("%d\n", DP[N][M]);    \\Outputting the final result.
    }
    else{
        for(int i=1; i<=M; ++i){
            for(int j=1; j<=N; ++j){
                if(j>i) break;
                if(j==1)DP[i][j]=abs(C[i]-B[j]);
                else{
                    tmp=DP[i-1][j-1]+abs(C[i]-B[j]);
                    DP[i][j]=(DP[i-1][j]!=-1)? min(tmp, DP[i-1][j]): tmp;
                }
            }
        }
        printf("%d\n", DP[M][N]);
    }
    return 0;
}
4

1 回答 1

3

Niels 的评论阐明，如果数组的大小相同，那么您应该对它们进行排序并将值配对。我们可以在此基础上构建一般情况：

我假设第一个数组的长度arr1小于或等于第二个数组的长度arr2。如果不是，请交换它们。首先，对两个数组进行排序，当你只考虑子数组和时，让成为dp[A][B]最小的差异（即从前到后）。你有两个选择：arr1[A...]arr2[B...]arr1Aarr2B

  • 对A和B。在这种情况下，您将得到|arr1[A]-arr2[B]| + dp[A+1][B+1].

  • 不要使用B. 请注意，在这种情况下，您将永远不会再考虑B（因为如果您将A和B与不同的元素配对，那么您可以交换两对并且总和会下降）。所以你可以简单地忽略B，你的答案将是dp[A][B+1]。

基本情况应该相当明显：

  • dp[length of arr1][length of arr2] = 0
  • dp[A][length of arr2] = infinity（不可能将 的其余元素配对arr1）。
于 2013-05-21T04:48:58.733 回答