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$的代价，如上决策即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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]);
}