http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_d
結局10111111...または111111...101となる文字列を見つける問題になるんですが、言い換えが甘くて場合分けをミスり、WAを量産しました。証明しながら解くことの重要性を感じた問題でした。
あとprevの情報を使うdpは覚えるものを複雑化するより、遷移を飛ばす感じにした方が実装楽そうですね。
int N; string str; int dp[MAX_N]; int nex[MAX_N]; void solve() { cin >> N >> str; str += "0"; nex[N] = N; rer(i, N, 0) { if(str[i + 1] == '0') nex[i] = i + 1; else nex[i] = nex[i + 1]; //debug(i, nex[i]); } rep(i, 0, N) { MAX(dp[i + 1], dp[i]); if(str[i] == '1') { if(nex[i] + 1 < N && str[nex[i] + 1] == '1') { MAX(dp[nex[i] + 2], dp[i] + nex[i] - i); } if(i + 1 < N && str[i + 1] == '0' && nex[i + 1] > i + 2) { MAX(dp[nex[i + 1]], dp[i] + nex[i + 1] - (i + 1) - 1); MAX(dp[nex[i + 1] - 1], dp[i] + nex[i + 1] - (i + 1) - 2); } } } cout << dp[N] << "\n"; }