Submission #8458856

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>

using namespace std;

typedef pair<char, int> P;

int N;
vector<int> A, B;
vector<P> in;

int dp[2001][2001];//Aがi番目まで整序されて、Bがj番目まで整序されてる時の最小手数
int costA[2000][2000], costB[2000][2000];
int cntA[2000], cntB[2000];

int main() {
	cin >> N;
	A.resize(N), B.resize(N), in.resize(2 * N);
	for (int i = 0; i < 2 * N; i++) {
		cin >> in[i].first >> in[i].second;
		in[i].second--;
	}

	for (int i = 0; i < 2 * N; i++) {
		int sumA[2001] = {}, sumB[2001] = {};
		for (int j = N - 1; j >= 0; j--) {
			sumA[j] = sumA[j + 1] + cntA[j];
			sumB[j] = sumB[j + 1] + cntB[j];
		}
		
		int num = in[i].second;
		for (int j = 0; j <= N; j++) {
			if (in[i].first == 'B') {
				costA[num][j] = sumA[num + 1] + sumB[j];
			}
			else {
				costB[j][num] = sumA[j] + sumB[num + 1];
			}

		}
		if (in[i].first == 'B')cntA[num]++;
		else cntB[num]++;
	}

	for (int i = 0; i <= N; i++)for (int j = 0; j <= N; j++)
		if (!(i == 0 && j == 0))dp[i][j] = 1145141919;
	dp[0][0] = 0;

	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= N; j++) {
			if (i + 1 <= N) {
				dp[i + 1][j] = min(dp[i][j] + costA[i][j], dp[i + 1][j]);
			}
			if (j + 1 <= N) {
				dp[i][j + 1] = min(dp[i][j] + costB[i][j], dp[i][j + 1]);
			}
		}
	}
	cout << dp[N][N] << endl;
	return 0;
}

Submission Info

Judge Result