メモ

自分に向けて書いたメモを取り扱っています.

JOI 2013-2014 予選4番

最近forで回すDPの方が書きやすい、と感じている

最初、鍵を持っている人の情報を持ってしまっていて重複したケースも数え上げてしまっていて時間が結構かかった。

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

const int MOD = 10007;

// J = 0bit, O = 1bit, I = 2bit
// i日目, 参加した人(bit表現)
int dp[1001][12];

int main() {
        map<char, int> D;
        D['J'] = 0, D['O'] = 1, D['I'] = 2;
        int N, ans = 0;
        string S;

        cin >> N >> S;

        for(int i = 0; i < 1 << 3; i++) {
                if(((i >> D[S[0]]) & 1) && ((i >> D['J']) & 1)) {
                        dp[0][i] = 1;
                }
        }

        for(int i = 1; i < N; i++) {
                for(int j = 0; j < 1 << 3; j++) {
                        for(int k = 0; k < 1 << 3; k++) {
                                for(int l = 0; l < 3; l++) {
                                        if((k >> D[S[i]] & 1) && ((k >> l) & 1) && ((j >> l) & 1))
                                        {
                                                dp[i][k] += dp[i-1][j];
                                                dp[i][k] %= MOD;
                                                break;
                                        }
                                }
                        }
                }
        }

        for(int i = 0; i < 1 << 3; i++) {
                ans += dp[N-1][i];
                ans %= MOD;
        }

        cout << ans << endl;
}