AT题面
简要题意
有一个红色的数轴,相邻两个整点之间连有一条边,所有边初始为红色。数轴上有 \(n\) 个棋子,将一个棋子从 \(a\) 位置移到 \(b\) 位置,可以将 \((a,b)\) 之间红边变为蓝边,蓝边变为红边。给定 \(k-1\) 条线段,问能否进行若干次操作,使得当 \(i\) 是奇数,第 \(i\) 条线段是蓝色,当 \(i\) 是偶数,第 \(i\) 条线段是红色。文章来源:https://www.toymoban.com/news/detail-450849.html
分析
将线段和棋子都排好序。
容易发现一个棋子最多朝一个方向走一定路程,不然反复走的那一段肯定多余。令 \(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}\)。文章来源地址https://www.toymoban.com/news/detail-450849.html
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;
}
到了这里,关于[ARC114D] Moving Pieces on Line 解题报告的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!