套路题。想要做类似的还可以做做 P6116。
对于不断交换两个数的操作，容易发现确定开始位置 和最终位置 ，操作次数固定为 。所以可以考虑对答案序列进行 dp。
容易想到设 为当前已经放好了前 个白色和 个黑色，最少需要多少次操作。则有状态转移方程：
其中 表示第 小的白/黑色球进行前面操作后坐在的位置。
然后观察此方程是否有后效性。容易发现，当前面的数固定时， 也是固定的。故方程无后效性。
进一步地，可以将 拆成其初始位置再分别加上移到它前面的黑/白球的数量。 预处理。最后 dp 即可。
code：
int n,m,e[N],c[N],d[N][2],cst[N][N][2],dp[N][N];
void Yorushika(){
scanf("%d",&n);
rep(i,1,n*2){
char op[3];
int x;
scanf("%s%d",op,&x);
c[i]=op[0]=='B';
e[i]=x;
d[x][c[i]]=i;
}
rep(i,1,n){
rep(j,1,n*2){
cst[j][i][0]=cst[j][i-1][0];
cst[j][i][1]=cst[j][i-1][1];
}
rep(j,1,d[i][0]){
cst[j][i][0]++;
}
rep(j,1,d[i][1]){
cst[j][i][1]++;
}
}
mems(dp,0x3f);
dp[0][0]=0;
rep(i,1,n*2){
rep(j,max(i-n,0),min(i,n)){
int k=i-j;
if(j)
dp[j][k]=min(dp[j][k],dp[j-1][k]+d[j][0]+cst[d[j][0]][j-1][0]+cst[d[j][0]][k][1]-i);
if(k)
dp[j][k]=min(dp[j][k],dp[j][k-1]+d[k][1]+cst[d[k][1]][k-1][1]+cst[d[k][1]][j][0]-i);
}
}
printf("%d\n",dp[n][n]);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}
