Algoogle

Algorithm for Programming Contest

AOJ 0595 Schedule

Category: AOJ Tag: dp

Schedule

問題概要


N日間, 毎日3人のうち誰が必ず来るか決まっている.
部室の鍵は最初Jが持っているが, 毎日持って帰るのはだれでもいい(ただし持って帰った場合は次の日来なければならない)
このときN日間の3人の出席パターンの数を求めよ.

解法


i日目に3人が出席するかどうかをビットで管理してbitDPする.
dp[i][j] := i日目の3人の出席状況j(ビットが立っていれば出席)
あとは必ず出席する人が出席しているとき, 次の状態とandを取って0でないならどちらにも出席している人が存在するのでその人が鍵を持って帰っていることにする(そうでないならそのようなパターンは存在しないので無視).
0日目はJだけが参加したことにすれば初日に鍵を持っているのはJにできる.
責任者はjのビットを見れば来ているかわかるので来ていないパターンは無視.

コード


(0595.cpp) download
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
38
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)

const int mod = 10007;
int N;
string str;
int p[1024];

void input(){
    cin >> N;
    cin >> str;
    rep(i,N) p[i] = str[i]=='J'? 1: str[i]=='O'? 2: 4;
}

int dp[1024][8];

int solve(){
    dp[0][1] = 1;
    rep(i,N) rep(j,8) if(p[i] & j)
        rep(k,8) if(j & k){
            dp[i+1][j] += dp[i][k];
            dp[i+1][j] %= mod;
        }
    int ans = 0;
    rep(i,8){
        ans += dp[N][i];
        ans %= mod;
    }
    return ans;
}

int main(){
    input();
    cout << solve() << endl;
    return 0;
}

Comments