AOJ0595 - Schedule
DPが出来なさすぎてつらいので練習
コード
// 8種類の選び方 N日のスケジュール int dp[8][1010]; const int mod = 1e4 + 7; int getid(char c) { if (c == 'J') return 0; if (c == 'O') return 1; return 2; } // 責任者が居ない場合を除外 void exclude(int now, int id) { REP(i, 8) { if ((i & (1 << id)) == 0) { dp[i][now] = 0; } } } signed main() { int N; string s; cin >> N >> s; REP(i, N) { // 一日目はJの参加が必須 if (i == 0) { REP(j, 8) dp[j][i] = 1; exclude(i, 0); } else { REP(j, 8) { REP(k, 8) { // 前日に居た人が一人でも居なければ飛ばす if (j & k) { dp[k][i] = (dp[k][i] + dp[j][i - 1]) % mod; } } } } exclude(i, getid(s[i])); } int ans = 0; REP(i, 8) { ans = (ans + dp[i][N - 1]) % mod; } print(ans); return 0; }
メモ
分からなかったのでJOIの解説を見ながら実装した.
dp[出席状況][何日目] = スケジュールの場合の数
を表す.
dp[k][i] = (dp[k][i] + dp[j][i - 1]) % mod
は前日までの場合の数( dp[j][i - 1]
)を足していく処理.
REP(j, 8) REP(k, 8)
の部分で昨日の出席状況に合わせ,ありうる今日の出席状況を全列挙している.(ここでは責任者がいない場合は考慮していない)
そのあとのexclude(i, getid(s[i]))
で責任者がいない出席状況のときの場合の数を0
にしている.
出席状況をbitで管理するのは面白いなぁと感じた.
こんな感じで1
が立ってるところは出席していると判断する.
I | O | J | |
---|---|---|---|
0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 |
2 | 0 | 1 | 0 |
3 | 0 | 1 | 1 |
4 | 1 | 0 | 0 |
5 | 1 | 0 | 1 |
6 | 1 | 1 | 0 |
7 | 1 | 1 | 1 |
exclude()
の中で責任者がいない場合を判断するために論理和を使っている.
if (j & k)
は前日に居た人が居なかったら飛ばす(鍵が無いので出席できないから)ところでも論理和を使って上手く判定している.
また配るDPは最後に足す処理があることが多いらしい.覚えておこう.