洛谷2507 [SCOI2008]配对

Luogu

算法

贪心+DP。

首先将$A$和$B$从小到大排个序。

设$f[i]$表示前$i$的元素的最小绝对值和。

显然,若$n=1$且$a[1]=b[1]$,则无解。

定义一个函数$calc(a,b)$,定义如下:

inline int calc(int a,int b) {
    if (a==b) return 233333333;
    else return abs(a-b);
}

它的作用是计算两个元素的差的绝对值,同时对于$a==b$直接返回$+\infty$。

边界:$f[1]=calc(a[1],b[1])$,$f[2]=min(calc(a[1],b[2]),calc(a[2],b[1]))$。

然后写状态转移。

容易发现,

对于一个位置,最优情况只会是a[i]对应b[i],b[i-1],b[i-2]组合的情况。

那么分5种情况大力DP。具体细节见代码。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

inline int Min(int a,int b) { if (a<b) return a; else return b; }

inline int calc(int a,int b) {
    if (a==b) return 233333333;
    else return abs(a-b);
}

int f[100010];
int a[100010],b[100010];

mainint main() {
    int n=read();
    for (re int i=1;i<=n;i++) a[i]=read(),b[i]=read();
    sort(a+1,a+n+1); sort(b+1,b+n+1);
    if (a[1]==b[1]&&n==1) { printf("-1\n"); return 0; }
    
    f[1]=calc(a[1],b[1]);
    f[2]=Min(f[1]+calc(a[2],b[2]),calc(a[1],b[2])+calc(a[2],b[1]));
    for (re int i=3;i<=n;i++) {
        f[i] = f[i-1] + calc(a[i],b[i]);
        f[i] = Min(f[i],f[i-2] + calc(a[i-1],b[i]) + calc(a[i],b[i-1]));
        f[i] = Min(f[i],f[i-3] + calc(a[i-2],b[i-1]) + calc(a[i-1],b[i]) + calc(a[i],b[i-2]));
        f[i] = Min(f[i],f[i-3] + calc(a[i-1],b[i-2]) + calc(a[i],b[i-1]) + calc(a[i-2],b[i]));
        f[i] = Min(f[i],f[i-3] + calc(a[i-2],b[i]) + calc(a[i],b[i-2]) + calc(a[i-1],b[i-1]));
    }
    
    printf("%lld\n",f[n]);
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 02 PM

2 条评论

  1. ZCDHJ

    高产似。。。

    1. M_sea
      @ZCDHJ

      做题做的快啊

发表评论