题解：P7194 [COCI2007-2008#6] CESTARINE

yx666 · 2024-05-12 12:53:15 · 题解

P7194 CESTARINE 题解

原题面传送门

Part 1：题意

Part 1.1：题目内容

给定两个长度为 n 的数列 a 和 b，满足同一数列中元素互不相同（a 对应题目中所有的入口，b 对应所有的出口）。

求将数列 a 随机打乱后，并满足 \forall i\in[1,n]，a_i\ne b_i 时，\sum_{i=1}^n \left|a_i-b_i\right| 的最小值。

Part 1.2：限制

• 时间：1 s，空间 32 MB，所有输入均为整数。

Part 2：思路

考虑 dp。

Part 2.1：定义问题状态

对 a、b 进行排序，接着设 f_k 表示将前 k 个出入口配对后的花费最小值，即：

Part 2.2：状态转移方程

定义函数 ckabs：

Part 2.2.1：a_i 与 b_i 配对：

Part 2.2.2：a_i,a_{i-1} 与 b_i,b_{i-1} 相互配对：

此时只用考虑 (a_i,b_{i-1}) 与 (a_{i-1},b_i)：

Part 2.2.3：三对数配对：

借助贪心的思想，发现：对于 a_i\footnotesize(i\in[2,n-1]) 最优的搭配，是将它与 b_{i-1}、b_i 或 b_{i+1} 搭配时（即让 a_{i-1},a_i,a_{i+1} 与 b_{i-1},b_i,b_{i+1} 互相搭配，花费最小时就是最优搭配）。

改一下下标，有以下三种搭配：

得到状态转移方程：

Part 2.2.4：四对数配对

重复了，因为四对数可以被拆成两个两对数。

Part 2.3：初始化与边界状态

• 初始化：注意下标，对 f_1，f_2 特殊关照：

• 边界状态：i=n。

Part 2.4：计算顺序与答案

• 计算顺序：1\to n。

• 答案：f_n。

Part 3：代码实现

注意开 long long。

#include<bits/stdc++.h>
using namespace std;

#define int long long

#define T int
inline T read(){T x=0;char ch=getchar();while(ch<'0'||'9'<ch) ch=getchar();while('0'<=ch&&ch<='9') {x=(x<<3)+(x<<1)+(ch-'0');ch=getchar();}return x;}
void write(T x){if(x>9) write(x/10);putchar(x%10+'0');return ;}
#undef T

constexpr int inf=0x3f3f3f3f;

inline int min(int x,int y){return x<y?x:y;}

#define N 100005
#define pii pair<int,int>

int n;
int a[N],b[N],f[N];
signed main(){
    n=read();
    for(int i=1;i<=n;++i){
        a[i]=read(),b[i]=read();
    }

    sort(a+1,a+1+n),sort(b+1,b+1+n);

    auto ckabs=[](int x){return x==0?inf:x<0?-x:x;};

    f[1]=ckabs(a[1]-b[1]);
    f[2]=min(f[1]+ckabs(a[2]-b[2]),ckabs(a[1]-b[2])+ckabs(a[2]-b[1]));
    for(int i=3;i<=n;++i){
        f[i]=f[i-1]+ckabs(a[i]-b[i]);
        f[i]=min(f[i],f[i-2]+ckabs(a[i]-b[i-1])+ckabs(a[i-1]-b[i]));
        f[i]=min(f[i],f[i-3]+ckabs(a[i]-b[i-1])+ckabs(a[i-1]-b[i-2])+ckabs(a[i-2]-b[i]));
        f[i]=min(f[i],f[i-3]+ckabs(a[i]-b[i-2])+ckabs(a[i-1]-b[i-1])+ckabs(a[i-2]-b[i]));
        f[i]=min(f[i],f[i-3]+ckabs(a[i]-b[i-2])+ckabs(a[i-1]-b[i])+ckabs(a[i-2]-b[i-1]));
    }
    write(f[n]);
    return 0;
}

AC 记录（目前最优解）。