[DP记录]AT4132 [ARC097C] Sorted and Sorted
command_block
2021-05-04 09:56:14
**题意** : 有 $2N$ 个球排成一列，其中有 $N$ 个黑球与 $N$ 个白球。把 $1$ 到 $N$ 这 $N$ 个数字分别写到 $N$ 个黑球上；白球亦然。
每次操作可以交换两个相邻的球。
使用尽量少的操作使得从左到右黑球，白球上的数字分别递增。回答这个最小的操作数。
$n\leq 2000$ ，时限$\texttt{2s}$。
------------
对于某组方案，记 $p_i$ 为在 $i$ 位置的球最后到达的位置，则交换的最小次数是 $p$ 的逆序对数。
也能发现， $p$ 的一个逆序对对应一对相对顺序改变的球。
黑球和白球内部的逆序对是常数，单独计算。于是只需最小化黑球和白球之间的““相对顺序改变的球对”。
接下来考虑 $\rm DP$。
记 $dp[i][j]$ 表示在最终序列中放置了写有 $1\sim i$ 的白球，写有 $1\sim j$ 的黑球，产生的“相对顺序改变的黑白球对”的数目的最小值。
转移显然，可见代码。复杂度 $O(n^2)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 2050
using namespace std;
const int INF=1000000000;
int n,p0[MaxN],p1[MaxN],o0[MaxN<<1][MaxN],o1[MaxN<<1][MaxN],dp[MaxN][MaxN];
char op;
int main()
{
scanf("%d",&n);
int sav=0;
for (int i=1,p;i<=n+n;i++){
scanf("%s%d",&op,&p);
for (int k=1;k<=n;k++)
{o0[i][k]=o0[i-1][k];o1[i][k]=o1[i-1][k];}
if (op=='W'){
p0[p]=i;sav+=o0[i][n]-o0[i][p];
for (int k=p;k<=n;k++)o0[i][k]++;
}else {
p1[p]=i;sav+=o1[i][n]-o1[i][p];
for (int k=p;k<=n;k++)o1[i][k]++;
}
}
for (int i=0;i<=n;i++)
for (int j=0;j<=n;j++)
dp[i][j]=INF;
dp[0][0]=0;
for (int i=0;i<=n;i++)
for (int j=0;j<=n;j++){
if (i>0)dp[i][j]=min(dp[i][j],dp[i-1][j]+o1[n+n][j]-o1[p0[i]][j]);
if (j>0)dp[i][j]=min(dp[i][j],dp[i][j-1]+o0[n+n][i]-o0[p1[j]][i]);
}
printf("%d",sav+dp[n][n]);
return 0;
}
```