CFR 404 D. Minesweeper 1D ( DP )

Problem - 404D - Codeforces

題意：
給一個字符串，裡面只有 0, 1, 2, *, ? 五種符號。如果是數字，表示左右的 * 個數加起來一定有那麼多。如果是 ? 代表未確定。求有幾種 ? 的代入方式使得序列合法，對 1e9 + 7 取模。

資料規模：
The first line contains sequence of characters without spaces s1s2... sn (1 ≤ n ≤ 1e6), containing only characters "*", "?" and digits "0", "1" or "2". If character si equals "*", then the i-th cell of the field contains a bomb. If character si equals "?", then Valera hasn't yet decided what to put in the i-th cell. Character si, that is equal to a digit, represents the digit written in the i-th square.

解法：
將 '*' 以 '3' 替代。
dp[ i ][ j ][ k ] : 已考慮前 i 個字符，倒數第二個字符確定為 j，最後一個字符確定為 k，此時的方案數

時間 / 空間複雜度：
O( | S | )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 1e6;
const int MOD = ( int ) 1e9 + 7;

string seq;
int dp[ MAXN + 1 ][ 3 + 1 ][ 3 + 1 ]; // 3 for bomb

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> seq;
  for( int i = 0; i < seq.size(); ++i ){
    if( seq[ i ] == '*' ){
      seq[ i ] = '3';
    }
  }
  dp[ 0 ][ 0 ][ 0 ] = 1;
  for( int i = 0; i < seq.size(); ++i ){
    for( int j = 0; j <= 3; ++j ){
      for( int k = 0; k <= 3; ++k ){
        for( int d = ( seq[ i ] == '?' ? 0 : seq[ i ] - '0' ); d <= ( seq[ i ] == '?' ? 3 : seq[ i ] - '0' ); ++d ){
          int kc = ( j == 3 ) + ( d == 3 );
          if( i != 0 and k < 3 and k != kc ) continue;
          if( i != 0 and d == 0 and k == 3 ) continue;
          ( dp[ i + 1 ][ k ][ d ] += dp[ i ][ j ][ k ] ) %= MOD;
        }
      }
    }
  }
  int ans = 0;
  for( int i = 0; i <= 3; ++i ){
    for( int j = 0; j <= 3; ++j ){
      if( j < 3 and ( i == 3 ) != j ) continue;
      ( ans += dp[ seq.size() ][ i ][ j ] ) %= MOD;
    }
  }
  cout << ans << endl;
  return 0;
}