bzoj1237 [SCOI2008]配对

Description

你有n 个整数Ai和n 个整数Bi。你需要把它们配对，即每个Ai恰好对应一个Bp[i]。要求所有配对的整数差的绝对值之和尽量小，但不允许两个相同的数配对。例如A={5,6,8}，B={5,7,8}，则最优配对方案是5配8, 6配5, 8配7，配对整数的差的绝对值分别为2, 2, 1，和为5。注意，5配5，6配7，8配8是不允许的，因为相同的数不许配对。

Input

第一行为一个正整数n，接下来是n 行，每行两个整数Ai和Bi，保证所有 Ai各不相同，Bi也各不相同。

Output

输出一个整数，即配对整数的差的绝对值之和的最小值。如果无法配对，输出-1。

Sample Input

3
3 65
45 10
60 25

Sample Output

HINT

1 <= n <= 10^5，Ai和Bi均为1到10^6之间的整数。

正解：$dp$。

因为每个数只出现一次，所以我们可以发现一个很显然的事，就是$a[i]$只会和$b[i-1],b[i],b[i+1]$匹配。

然后我们就可以$dp$了。设$f[i]$表示匹配了前$i$位的最小值。

于是$f[i]=max(f[i-1]+val,f[i-2]+val,f[i-3]+val)$，$val$为对应权值，当然还要判断一下合法性。

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 #define inf (1LL<<60)
 6 #define N (100010)
 7 
 8 using namespace std;
 9 
10 int a[N],b[N],p[3],n;
11 ll f[N];
12 
13 il int gi(){
14   RG int x=0,q=1; RG char ch=getchar();
15   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
16   if (ch=='-') q=-1,ch=getchar();
17   while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
18   return q*x;
19 }
20 
21 int main(){
22 #ifndef ONLINE_JUDGE
23   freopen("match.in","r",stdin);
24   freopen("match.out","w",stdout);
25 #endif
26   n=gi(); for (RG int i=1;i<=n;++i) a[i]=gi(),b[i]=gi();
27   sort(a+1,a+n+1),sort(b+1,b+n+1);
28   if (n==1){
29     if (a[1]==b[1]) puts("-1");
30     else cout<<abs(a[1]-b[1]); return 0;
31   }
32   for (RG int i=1;i<=n;++i){
33     f[i]=inf; if (a[i]!=b[i]) f[i]=min(f[i],f[i-1]+abs(a[i]-b[i]));
34     if (i>=2){
35       if (a[i]!=b[i] && a[i-1]!=b[i-1])
36     f[i]=min(f[i],f[i-2]+abs(a[i]-b[i])+abs(a[i-1]-b[i-1]));
37       else f[i]=min(f[i],f[i-2]+abs(a[i]-b[i-1])+abs(a[i-1]-b[i]));
38     }
39     if (i>=3){
40       p[0]=0,p[1]=1,p[2]=2;
41       do{
42     if (a[i]!=b[i-p[0]] && a[i-1]!=b[i-p[1]] && a[i-2]!=b[i-p[2]])
43       f[i]=min(f[i],f[i-3]+abs(a[i]-b[i-p[0]])+abs(a[i-1]-b[i-p[1]])+abs(a[i-2]-b[i-p[2]]));
44       }while (next_permutation(p,p+3));
45     }
46   }
47   cout<<f[n]; return 0;
48 }