洛谷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\n",dp[n]),0;
}