2/5 日記

え、今日1問しかといてないのか　絶句

・N マス目のなんたら

bitDP。普通に上から一つずつやると中央値の判定がうまくいかない。i行目の状態を表すbit列をbiとしたとき、bi-1、bi+1が存在する事がbiの成立条件となる。よって、

dp[j][b]を、j行目まで見たときに、j-1行目とj行目のbit列をbとし、j-1行目について中央値の条件が成り立つものの個数とすればよい。

マス目の外は全て0なので、このdpを自然に更新していけば解ける。

すばすば