首页 > 代码库 > BZOJ 1237 配对（DP）

BZOJ 1237 配对（DP）

2024-07-09 00:01:22   220人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1237

题意：给出两个n元素的数列A和B。为A中的每个元素在B中为其找一个配对的元素（配对的元素不能相等，B中每个元素只能被使用一次），使得所有配对的两个数的差的绝对值之和最小？

思路：首先排序，若无配对元素不能相等这一 限制，则排序后一一匹配即可。有了这个限制，那么对于相等的元素就要在其前后进行调整，显然，与距离较远的调整不如与距离近的调整优。那么，需要在多大的 范围内调整才能保证最优呢？大牛给出的结论是最多在上下三个元素内调整即可。我不会证明。。不过，两个肯定是不行的，比如n=3，三个元素均对应相等，此 时必须要三个元素之间调整。那么，若4个连续元素对应相等呢？此时前两个调整后两个调整即可得到最优。因此用不着四个调整。这只是我粗糙的理解。这样的话 DP即可。f[i]表示前i个元素匹配完的最优值。

 

i64 f[N];int a[N],b[N],n;i64 C(int x){    if(x==0) return inf;    return abs(x);}int main(){    RD(n);    int i;    FOR1(i,n) RD(a[i],b[i]);    sort(a+1,a+n+1);     sort(b+1,b+n+1);    f[1]=C(a[1]-b[1]);    f[2]=min(f[1]+C(a[2]-b[2]),C(a[1]-b[2])+C(a[2]-b[1]));    for(i=3;i<=n;i++)    {        f[i]=f[i-1]+C(a[i]-b[i]);        f[i]=min(f[i],f[i-2]+C(a[i]-b[i-1])+C(a[i-1]-b[i]));        f[i]=min(f[i],f[i-3]+min(C(a[i]-b[i-1])+C(a[i-1]-b[i-2])+C(a[i-2]-b[i]),                                 C(a[i]-b[i-2])+C(a[i-1]-b[i])+C(a[i-2]-b[i-1])));    }      if(f[n]>=inf) puts("-1");    else PR(f[n]);}

 

 

 


联系
我们