[DP记录]ARC114D Moving Pieces on Line
command_block
2021-10-28 16:35:56
**题意** ：数轴上有 $n$ 个球 ，第 $i$ 个球位置为 $x_i$ 。
初始时，数轴全为白色。可以每次选择一个球向左或者向右滚一段距离，且将滚过的部分反色。
给定 $k$ 个不交的区间，要求恰将这些区间染成黑色。
求球滚过的最小总距离，或指出无解。
$n,k\leq 5000$ ，时限$\texttt{2s}$。
------------
不难发现，在最优方案中，对于单独某个球，其滚动不可能回头，相当于只滚了一次。
区间操作不便处理，用 xor 差分转化问题。
记 $e_i$ 为区间 $[i,i+1)$ ，目标状态相当于指定若干个 $e$ 为黑色。
将位于 $x_i$ 的球滚到 $t_i$ ，相当于给 $e_{x_i},e_{t_i}$ 各异或上 $1$ ，代价为 $|x_i-t_i|$ 。
这里 $e_{x_i}$ 处的异或操作是确定的，预先计算。然后序列中剩余的 $1$ 就是 $e_{t_i}$ 需要放的位置。
剩下的问题就是：
数轴上有若干个红点（$x_i$），若干个蓝点（剩余需要 xor 的位置），找出一个匹配（蓝点不能匹配蓝点，其余都行），使得距离和最小。
（蓝红匹配就是用 $e_{t_i}$ 去填剩余需要 xor 的位置，红红匹配是因为红点太多，内部抵消掉一些）
若蓝点数大于红点数则无解（蓝红点数奇偶性不同也无解，不过题目保证没有这种情况）。先考虑蓝红点数相等的情况。
不难发现，一对交叉的匹配可以不劣地调整为一对不交叉的匹配，于是一定存在一种最优解是不交叉的。
将红蓝点分别排序，按排名对位匹配即可。
接着考虑红点多余的情况，若我们钦定了一个红点的匹配集合，必然是内部相邻的匹配，外部按排名匹配。
可以发现，若两个排名不相邻的红点匹配，可以不劣地调整成两个排名相邻的红点匹配。
记 $dp_{i,j}$ 表示前 $i$ 个红点匹配了前 $j$ 个蓝点的最小代价。转移有两类：一蓝一红，相邻两红。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 5050
using namespace std;
int n,m,x[MaxN],y[MaxN<<1];
ll dp[MaxN][MaxN];
int main()
{
scanf("%d%d",&n,&m);m+=n;
for (int i=1;i<=n;i++){scanf("%d",&x[i]);y[i]=x[i];}
for (int i=n+1;i<=m;i++)scanf("%d",&y[i]);
sort(x+1,x+n+1);sort(y+1,y+m+1);
int tn=0;
for (int i=1,las=1;i<=m;i++)
if (i==m||y[i]!=y[i+1]){
if ((i-las+1)&1)y[++tn]=y[i];
las=i+1;
}
m=tn;
if (m>n){puts("-1");return 0;}
for (int i=1;i<=n;i++)
for (int j=0;j<=min(i,m);j++)if (!((i-j)&1)){
dp[i][j]=dp[i-1][j-1]+(x[i]<y[j] ? y[j]-x[i] : x[i]-y[j]);
if (i-2>=j)dp[i][j]=min(dp[i][j],dp[i-2][j]+x[i]-x[i-1]);
}
printf("%lld",dp[n][m]);
return 0;
}
```