CODE FESTIVAL qual B - D 101 to 010

• 問題

問題概要

ビット列Sが与えられる。
"101" -> "010" の変換ができる。最大何回できるか。

解法

dp[i] = (i番目までの文字で最大何回変換できるか) とおく。
変換には二種類あり、もともとある101を変換するか、変換によってできた101を変換するかである。
後者は、101の前または後ろに1が並んでいるケースに限られる。
ex1. 10111 -> 01011 -> 00101 -> 00000
ex2. 11101 -> 11010 -> ...
よって101を見つけて、前後に1の列があればその変換から広がるdp[i]の値の変化を追っていけばいいことがわかる。
またSの前後に番兵の'0'を置いておくと末端の処理を書かなくていいので楽。

メモ

DPっぽいというのはわかったが、書けなかった...
やるだけとか言えるようになりたい

コード

#include<stdio.h>
#include<iostream>
#include<string>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 500005;
const ll lmod = 1e9+7;

int dp[MAX_N];

int main(){
  int N;
  string S;
  cin >> N >> S;
  fill(dp,dp+N,0);
  S = "0" + S + "0";
  REP(i,1,N+1){
    dp[i+1] = max(dp[i],dp[i+1]);
    if(S[i-1]=='1'&&S[i]=='0'&&S[i+1]=='1'){
      int a,b;
      a = i-1;
      b = i+1;
      while(1){
        if(S[a]=='0') break;
        dp[i+1] = max(dp[i+1],dp[a-1]+i-a);
        a--;
      }
      while(1){
        if(S[b]=='0') break;
        dp[b] = max(dp[b],dp[i-2]+b-i);
        b++;
      }
    }
  }
  // rep(i,N+2) cout << dp[i] << ",";
  // cout << "" << endl;
  // rep(i,N+2) cout << S[i] << ",";
  // cout << "" << endl;
  cout << dp[N+1] << endl;
  return 0;
}