SRM 650 div2 Med

問題概要

'A','B','?'で構成される文字列がある。全ての'?'を'A'または'B'で置き換えたとき、最終的な得点を最小化せよ。得点は、連続する文字列で"AA"または"BB"となるものが1pointである。ただし、overlapも考えるので、"BBB"は2pointとなる。

制約

• 1 ≤ |S| ≤ 50

解法

dpする。
dp[何文字目]['A'or'B'] := 最小の得点。

コード

#define INF 1e9

class TaroFillingAStringDiv2 {
public:
  int getNumber(string S) {
    int len = S.size();
    int dp[51][2];
    fill(dp[0],dp[0]+51*2,INF);
    if(S[0] == 'A'){
      dp[0][0] = 0;
    }else if(S[0] == 'B'){
      dp[0][1] = 0;
    }else{
      dp[0][0] = dp[0][1] = 0;
    }
    for(int i = 1 ; i < len ; i++){
      if(S[i] == '?'){
        dp[i][0] = min(dp[i-1][0]+1,dp[i-1][1]);
        dp[i][1] = min(dp[i-1][0],dp[i-1][1]+1);
      }else if(S[i] == 'A'){
        dp[i][0] = min(dp[i-1][0]+1,dp[i-1][1]);
      }else{
        dp[i][1] = min(dp[i-1][0],dp[i-1][1]+1);
      }
    }
    return min(dp[len-1][0],dp[len-1][1]);
  }
};