ARC114 - Moving Pieces on Line

题目大意：

白色的数轴上有 \(n\) 个球 \(a_i\) ，给定若干递增且不交的区间 \([t_i,t_{i+1})\)

每次选择一个球向左或者向右滚，且将滚过的一段反色

求最小步数恰好仅将给定区间染黑色，或者确定不存在方案

模型转化

首先显然可以发现，每个小球只会滚过一段区间一次

设小球 \(i\) 最终停在 \(b_i\) ，则滚过这段数轴会被反色，且代价为 \(|a_i-b_i|\)

将最终颜色做异或差分，那么对于目标的反色，我们认为就是在每个 \(t_i\) 处放置了一个1

而对于所有 \(a_i\) ，就是在 \(a_i,b_i\) 处分别放置了一个1，这样就完全避免了关于 \(a_i,b_i\) 大小关系的问题

计算答案

由于已经固定了 \(a_i\) (设 \(a_i\) 已经排好序)，我们需要决策 \(b_i\)

那么可以预先得到哪些位置需要放置奇数个 \(b_i\) ，设这个集合为 \(pos\)

若 \(|pos|>n\) ，显然无解

否则， \(b_i\) 的放置仅有两种情况

1.放在某一个 \(pos_i\) 处

2.让两个 \(b_i\) 放在同一个位置

对于 \(a,pos\) 排序之后的情况，显然较小的 \(a_i\) 会匹配较小的 \(pos_i\) ，代价为 \(|a_i-pos_i|\)

而情况2用掉的两个 \(b_i\) ，选择使用 \(b_i,b_{i+1}\) 一定不劣，并且代价就是 \(a_{i+1}-a_i\)

那么令 \(dp_{i,j}\) 表示前 \(i\) 个 \(a_i\) ，已经匹配了 \(j\) 个 \(pos_j\) 的代价，如上决策即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=5010,P=998244353;

int n,m;
int a[N],b[N];
ll dp[N][N];
int h[N*2],hc;
int s[N*2],t[N*2];
int pos[N*2],c;

int main(){
	n=rd(),m=rd();
	rep(i,1,n) a[i]=rd(),h[++hc]=a[i];
	rep(i,1,m) b[i]=rd(),h[++hc]=b[i];
	sort(a+1,a+n+1);
	sort(h+1,h+hc+1),hc=unique(h+1,h+hc+1)-h-1;
	rep(i,1,n) {
		a[i]=lower_bound(h+1,h+hc+1,a[i])-h;
		s[a[i]]^=1;
	}
	rep(i,1,m) {
		b[i]=lower_bound(h+1,h+hc+1,b[i])-h;
		t[b[i]]^=1;
	}
	rep(i,1,hc) if(s[i]^t[i]) pos[++c]=i;
	if(c>n || (n-c)&1) return puts("-1"),0;
	memset(dp,63,sizeof dp),dp[0][0]=0;
	rep(i,1,n) rep(j,0,min(i,c)) {
		if(j<c) cmin(dp[i][j+1],dp[i-1][j]+abs(h[a[i]]-h[pos[j+1]]));
		if(i<n) cmin(dp[i+1][j],dp[i-1][j]+h[a[i+1]]-h[a[i]]);
	}
	printf("%lld\n",dp[n][c]);
}