洛谷P2507 [SCOI2008]配对 题解（dp+贪心）

洛谷P2507 [SCOI2008]配对 题解（dp+贪心）

标签：题解
阅读体验：https://zybuluo.com/Junlier/note/1299251

链接题目地址：洛谷P2507 [SCOI2008]配对

感觉是道很好的推断题

贪心

想到贪心的结论就很容易，没想到就很难做出来了
结论：对(A,B)数组分别排序之后，在(A)中选第(i)个数，与之配对的数一定在(B[i-1])~(B[i+1])内
其实证明是很好证的，在与你是否往这方面想了。。。

因为题目有一个很好的性质：(A,B)数列中数字各不相同
所以如果没有配对不相等的限制的话，我们肯定是排序直接减得答案是吧
那么有限制之后，就有机会让(A[i])和(B[i-1])或(B[i+1])配对了吧，跳远了显然是不会更优的

动态规划

那么就可以直接(dp)了：(dp[i])表示到第(i)号全部配对的最小答案
因为一个数可能与三个数配对，那么我们可以大力讨论(dp)了
对于限制，我们手写一个(ABS)，如果差为0，返回(Inf)就(ok)

dp[i]=MIN(dp[i],dp[i-1]+ABS(A[i]-B[i]));
dp[i]=MIN(dp[i],dp[i-2]+ABS(A[i]-B[i-1])+ABS(A[i-1]-B[i]));
dp[i]=MIN(dp[i],dp[i-3]+ABS(A[i]-B[i-1])+ABS(A[i-1]-B[i-2])+ABS(A[i-2]-B[i]));
dp[i]=MIN(dp[i],dp[i-3]+ABS(A[i]-B[i-2])+ABS(A[i-1]-B[i-1])+ABS(A[i-2]-B[i]));
dp[i]=MIN(dp[i],dp[i-3]+ABS(A[i]-B[i-2])+ABS(A[i-1]-B[i])+ABS(A[i-2]-B[i-1]));

从上到下依次是：自己看一下吧。。。（草稿纸上玩结论，自己(yy)，我懒得写了）

那么全部代码

不合法情况就是(n==1)并且(A[1]==B[1])时
因为(A,B)数列中数字各不相同，所以(n>1)时一定可以另外配得到对

#include<bits/stdc++.h>
#define il inline
#define rg register
#define ldb double
#define lst long long
#define rgt register int
#define N 100050
using namespace std;
const lst Inf=1e15;
il int MAX(rgt x,rgt y){return x>y?x:y;}
il lst MIN(rg lst x,rg lst y){return x<y?x:y;}
il int read()
{
    int s=0,m=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
    while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return m?-s:s;
}

int n;
lst A[N],B[N];lst dp[N];
il lst ABS(rg lst x){return x?(x>0?x:-x):(Inf);}

int main()
{
    n=read();
    for(rgt i=1;i<=n;++i)A[i]=read(),B[i]=read(),dp[i]=Inf;
    if(n==1&&A[1]==B[1]){puts("-1");return 0;}
    sort(&A[1],&A[n+1]),sort(&B[1],&B[n+1]);
    dp[1]=ABS(A[1]-B[1]);
    dp[2]=MIN(dp[1]+ABS(A[2]-B[2]),ABS(A[1]-B[2])+ABS(A[2]-B[1]));
    for(rgt i=3;i<=n;++i)
    {
        dp[i]=MIN(dp[i],dp[i-1]+ABS(A[i]-B[i]));
        dp[i]=MIN(dp[i],dp[i-2]+ABS(A[i]-B[i-1])+ABS(A[i-1]-B[i]));
        dp[i]=MIN(dp[i],dp[i-3]+ABS(A[i]-B[i-1])+ABS(A[i-1]-B[i-2])+ABS(A[i-2]-B[i]));
        dp[i]=MIN(dp[i],dp[i-3]+ABS(A[i]-B[i-2])+ABS(A[i-1]-B[i-1])+ABS(A[i-2]-B[i]));
        dp[i]=MIN(dp[i],dp[i-3]+ABS(A[i]-B[i-2])+ABS(A[i-1]-B[i])+ABS(A[i-2]-B[i-1]));
    }return printf("%lld
",dp[n]),0;
}