简要题意
有一个红色的数轴，相邻两个整点之间连有一条边，所有边初始为红色。数轴上有 \(n\) 个棋子，将一个棋子从 \(a\) 位置移到 \(b\) 位置，可以将 \((a,b)\) 之间红边变为蓝边，蓝边变为红边。给定 \(k-1\) 条线段，问能否进行若干次操作，使得当 \(i\) 是奇数，第 \(i\) 条线段是蓝色，当 \(i\) 是偶数，第 \(i\) 条线段是红色。
分析
容易发现一个棋子最多朝一个方向走一定路程，不然反复走的那一段肯定多余。令 \(x_i\) 表示点 \(i\) 左右两条线段是否相同，那么一个棋子移动就相当于一个区间异或操作，将其差分，就变成了起始点异或 \(1\)，终止点异或 \(1\)。因为线段的端点均是 \(x_i=1\)，所以只有被异或奇数次的才有可能是终止点，假设这样的点有 \(m\) 个。
根据上面的分析，可以知道 \(m\) 一定小于等于 \(n\)。
对于 \(m\le n\) 的情况，将棋子的位置看作白点，将异或奇数次的点看作黑点。首先黑白点能互相匹配，代价为 \(|a_i-b_j|\)；相邻的白白点也可以互相匹配，代价为 \(a_i-a_{i-1}\)。令 \(f_{i,j}\) 表示 \(i\) 个白点和 \(j\) 个黑点匹配的代价，直接dp，答案为 \(f_{n,m}\)。
Code
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=5e3+10;
int n,m,a[N],b[N<<1],c[N<<1],cnt;
ll f[N][N];
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(m);
for(int i=1;i<=n;i++){
read(a[i]);
b[i]=a[i];
}
for(int i=1;i<=m;i++){
read(b[i+n]);
}
m+=n;
sort(a+1,a+n+1);
sort(b+1,b+m+1);
for(int i=1,j;i<=m;i=j){
for(j=i;j<=m;j++){
if(b[j]!=b[i]){
break;
}
}
if((j-i)%2){
c[++cnt]=b[i];
}
}
if(n<cnt){
puts("-1");
return 0;
}
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=cnt;j++){
if(j)f[i][j]=f[i-1][j-1]+abs(a[i]-c[j]);
if(i>=2){
f[i][j]=min(f[i][j],f[i-2][j]+a[i]-a[i-1]);
}
}
}
write_endl(f[n][cnt]);
return 0;
}