[AtCoder ARC097]E - Sorted and Sorted（dp，逆序对，前缀和优化）

Posted on | In
AtCoder ARC097.E

E - Sorted and Sorted

Time limit : 2sec / Memory limit : 1024MB
Score : 600 points

Problem Statement

There are $2N$ balls, $N$ white and $N$ black, arranged in a row. The integers from $1$ through $N$ are written on the white balls, one on each ball, and they are also written on the black balls, one on each ball. The integer written on the $i$-th ball from the left ($1 ≤ i ≤ 2N$) is $a_i$, and the color of this ball is represented by a letter $c_i$. $c_i = $ W represents the ball is white; $c_i = $B represents the ball is black.
Takahashi the human wants to achieve the following objective:

  • For every pair of integers $(i,j)$ such that $1 ≤ i < j ≤ N$, the white ball with $i$ written on it is to the left of the white ball with $j$ written on it.
  • For every pair of integers $(i,j)$ such that $1 ≤ i < j ≤ N$, the black ball with $i$ written on it is to the left of the black ball with $j$ written on it.

In order to achieve this, he can perform the following operation:

  • Swap two adjacent balls.

Find the minimum number of operations required to achieve the objective.

Constraints

$1 ≤ N ≤ 2000$
$1 ≤ a_i ≤ N$
$c_i = $ W or $c_i =$ B.
If $i ≠ j$, $(a_i,c_i) ≠ (a_j,c_j)$.

Input

Input is given from Standard Input in the following format:

$N$
$c_1$ $a_1$
$c_2$ $a_2$
$:$
$c_{2N}$ $a_{2N}$

Output

Print the minimum number of operations required to achieve the objective.

Samples

Input Output
3
B 1
W 2
B 3
W 1
W 3
B 2
 4
4
B 4
W 4
B 3
W 3
B 2
W 2
B 1
W 1		 18
9
W 3
B 1
B 4
W 1
B 5
W 9
W 2
B 6
W 5
B 3
W 8
B 9
W 7
B 2
B 8
W 4
W 6
B 7		 41

Sample 1:
The objective can be achieved in four operations, for example, as follows:
Swap the black 3 and white 1.
Swap the white 1 and white 2.
Swap the black 3 and white 3.
Swap the black 3 and black 2.

解题思路

先看一个最基本的问题：

已知 $1$ 到 $N$ 的一个排列，每次操作可以交换相邻两数，求至少多少次操作才能将这个数列变为 $1,2,3,\cdots,N$

答案就是原数列的逆序对对数。证明如下：
目标数列显然满足这样一个性质：对于 $\forall i \in [1,N)$，都有 $a_i < a_{i+1}$。因此如果当前数列不是目标数列，一定 $\exists\ i \in [1,n)$ 使得 $a_i > a_{i+1}$，那么 $a_i$ 和 $a_{i+1}$ 就构成了一对逆序对，我们需要一次操作交换这两个数。这样周而复始地进行交换操作，最终操作数量就是逆序对对数。

这个基本问题就可以衍生出许多问题，比如说 NOIP2013花匠 [题解]，又比如这道题。

这道题把一个 $1$ 到 $N$ 的排列变成了两个 $1$ 到 $N$ 的排列相混合，于是出现了一个问题：我们甚至都不知道最终数列的状态是怎样的。
假设现在我们知道最终数列的状态，那么只需要像 NOIP2013花匠 一样扩展一下“逆序对” $(a_i,a_j)$ 的定义为：初始时 $a_i$ 在 $a_j$ 之后，目标状态下 $a_i$ 在 $a_j$ 之前的一对 $(a_i,a_j)$。这样，答案仍旧是逆序对对数。
ok，现在我们只需要找到最优的目标状态了：

  • dp状态：定义 $dp[i][j]$ 表示目标状态中，前 $i+j$ 个数由 $1$~$i$ 的黑球和 $1$~$j$ 的白球混合排列而成（对于任意一种颜色的球，排列是升序的）时，最少的逆序对对数
  • dp方程：$dp[i][j] = min(dp[i-1][j] + b_{i,j},dp[i][j-1] + w_{i, j})$，其中 $b_{i,j}$ 表示 $1$~$i$ 的白球和 $1$~$j$ 的黑球中，初始时在黑球 $i$ 之后的球的数量；$w_{i,j}$ 同理
    具体计算 $b_{i,j}$ 和 $w_{i,j}$ 可以在 dp 之前先 $O(N^2)$ 预处理出所有位置关系，再通过二维前缀和优化使得能够在 dp 时 $O(1)$ 得值
  • dp顺序：由dp方程易知：顺序 for i 再 for j 即可
  • 边界条件：由dp定义和dp顺序可知：dp[0][0] = 0

答案即是 $dp[N][N]$

时间复杂度：$O(N^2)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int INF = 0x7fffffff;
const int N = 2005;
int n, a[N<<1], t, dp[N][N], g[N<<1][N<<1];
char c;

int cal(int x, int b, int w){
	return g[x][b] - g[x-1][b] + g[x][w] - g[x][n] - g[x-1][w] + g[x-1][n];
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n << 1; i++){
		scanf("%s%d", &c, &a[i]);
		if(c == 'W')	a[i] += n;
		for(int j = 1; j < i; j++)
			g[a[j]][a[i]] = 1;
	}
	for(int i = 1; i <= n << 1; i++)
		for(int j = 1; j <= n << 1; j++)
			g[i][j] += g[i-1][j] + g[i][j-1] - g[i-1][j-1];
	memset(dp, 0x7f, sizeof dp);
	dp[0][0] = 0;
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			if(!i && !j)	continue;
			dp[i][j] = min(i ? dp[i-1][j] + cal(i, i, j+n) : INF, j ? dp[i][j-1] + cal(j+n, i, j+n) : INF);
		}
	}
	printf("%d\n", dp[n][n]);
	return 0;
}