[ARC114D] Moving Pieces on Line 题解

题目链接

点击打开链接

题目解法

有点牛的题，前面的转化感觉很妙

首先一个显然的性质是：一个棋子不可能走回头路，不然前面的路就白走了

下面是最妙的一步：我们令 \(st_i\) 为 \(i-1\to i\) 和 \(i\to i+1\) 的颜色是否相同，那么问题可以转化成：选择 \(\{p_i\}\)，一开始所有点颜色为 \(0\)，将 \(a_i\) 和 \(p_i\) 反转颜色，最后使 \(\{t_i\}\) 的颜色为 \(1\) 的最小 \(\sum\limits_{i=1}^n |a_i-p_i|\)

这个问题就好入手了
继续简化问题
我们把 \(\{a_i\}\) 和 \(\{t_i\}\) 集合合在一起，把出现次数为奇数的位置提出来，令其为 \(\{b_1,b_2,...,b_m\}\)
考虑如何把这个东西和原问题对应？我们要寻找一个完美匹配，匹配方式为：要么 \(a_i\) 和 \(a_j\) 匹配，要么 \(a_i\) 和 \(b_j\) 匹配，权值为匹配双方的差的绝对值之和

• \(n<m\) 显然无解
• \(n\ge m\)
  默认 \(a,b\) 从小到大排好序
  考虑一个贪心的思路是：如果 \(a\) 中的两个匹配，那么只可能是相邻的，然后 \(a\) 中未匹配的从小到大依次和 \(b\) 中的匹配
  不难得到 \(nm\) 的 \(dp\)

时间复杂度 \(O(nm)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=5010;
int n,k,a[N],b[N],rig[N];LL f[N][N];
map<int,bool> mp;
int main(){
    n=read(),k=read();
    F(i,1,n) a[i]=read(),mp[a[i]]^=1;
    F(i,1,k) b[i]=read(),mp[b[i]]^=1;
    int len=0;
    for(auto it:mp) if(it.second){
        if(len+1>=N){ puts("-1");exit(0);}
        rig[++len]=it.first;
    }
    if(len>n||((n-len)&1)){ puts("-1");exit(0);}
    sort(a+1,a+n+1);
    ms(f,0x3f);
    f[0][0]=0;
    F(i,1,n) F(j,0,len){
        if(i>=2) chkmin(f[i][j],f[i-2][j]+abs(a[i]-a[i-1]));
        if(j) chkmin(f[i][j],f[i-1][j-1]+abs(a[i]-rig[j]));
    }
    printf("%lld\n",f[n][len]);
    return 0;
}