Submission #3920423

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <set>
using namespace std;

int dp[2002][2002];
int cnt_white[2002][4002];
int cnt_black[2002][4002];

int main(){
    int N;
    cin >> N;
    map<int, int> white, black;
    for(int i=0; i<2*N; i++){
        char c;
        int a;
        cin >> c >> a;
        if(c == 'W') white[a] = i+1;
        else black[a] = i+1;
    }

    int aa[4002];
    fill_n(aa, 4002, 0);
    for(int i=N; i>=1; i--){
        aa[white[i]] = 1;
        for(int j=1; j<=2*N; j++)
            cnt_white[i][j] = cnt_white[i][j-1] + aa[j];
    }
    fill_n(aa, 4002, 0);
    for(int i=N; i>=1; i--){
        aa[black[i]] = 1;
        for(int j=1; j<=2*N; j++)
            cnt_black[i][j] = cnt_black[i][j-1] + aa[j];
    }

    for(int i=0; i<=N; i++)
        for(int j=0; j<=N; j++)
            dp[i][j] = 1<<30;
    dp[0][0] = 0;

    for(int i=0; i<2*N; i++){
        for(int w=0; w<=i; w++){
            int b = i - w;
            if(b > N || w > N) continue;
            if(w < N)
                dp[w+1][b] = min(dp[w+1][b], dp[w][b] + cnt_white[w+2][white[w+1]] + cnt_black[b+1][white[w+1]]);
            if(b < N)
                dp[w][b+1] = min(dp[w][b+1], dp[w][b] + cnt_black[b+2][black[b+1]] + cnt_white[w+1][black[b+1]]);
        }
    }
    cout << dp[N][N] << endl;
    return 0;
}

Submission Info

Judge Result