Submission #3013460

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int NMAX = 2005;
const int INF = 1000000000;

int n, a[NMAX], b[NMAX], mma[2 * NMAX][NMAX], mmb[2 * NMAX][NMAX], dp[NMAX][NMAX];
int main()
{
	cin >> n;
	for (int i = 1; i <= 2 * n; i++)
    {
        char c;
        int x;
		cin >> c >> x;
		c == 'W' ? a[x] = i : b[x] = i;

		for (int j = 0; j < n; j++)
        {
			mma[i][j] = mma[i - 1][j];
            mmb[i][j] = mmb[i - 1][j];
			c == 'W' ? mma[i][j] += x > j : mmb[i][j] += x > j;
		}
	}

	for (int j = 1; j <= n; j++)
        dp[0][j] = INF;

	for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
        {
            if (i)
                dp[i][j] = dp[i - 1][j] + mma[a[i]][i] + mmb[a[i]][j];
            if (j)
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + mma[b[j]][i] + mmb[b[j]][j]);
        }
	cout << dp[n][n];
	return 0;
}

Submission Info

Judge Result