https://atcoder.jp/contests/joi2014yo/tasks/joi2014yo_d
NOTE
Sorry. This problem is in Japanese.
How to solve it?
dp[i][S] := The number of possible schedule for the case where the state of the club member is
Son dayi.dp[i][S] = (total number of patterns meeting the previous day's conditions) % 10_007
Solution
use proconio::input;
pub fn main() {
input!(
n: usize,
s: String,
);
let s = s.chars();
let base = 10_007;
// dp[date][universal set]
let mut dp = vec![vec![0; 1 << 3]; n + 1];
// Jが出席して、1日の場合のパターンは1つしかない
dp[0][1] = 1;
for (i, c) in s.enumerate() {
let must = match c {
'J' => 1,
'O' => 1 << 1,
'I' => 1 << 2,
_ => panic!(),
};
for prev_j in 0..1 << 3 {
for j in 0..1 << 3 {
if must & j > 0 && prev_j & j > 0 {
dp[i + 1][j] += dp[i][prev_j];
dp[i + 1][j] %= base;
}
}
}
}
println!("{}", dp[n].iter().sum::<usize>() % base);
}
if must & j > 0 && prev_j & j > 0 {
dp[i + 1][j] += dp[i][prev_j];
dp[i + 1][j] %= base;
}
The conditional statement of this expression is,
- The representative is in the subset
j, - The same person is a participant of the previous day (prev_j) and the same person on the day of the event to give the key. Counted only in the above cases.
Top comments (0)