每日一题：皇家烈焰（线性dp）

题意

现在帕秋莉告诉你一部分烈焰的分布情况，请你告诉她可能的情况有多少种

对于一个格子，里面会有以下几种字符：

0：这个格子没有烈焰，且其左右两个格子均没有烈焰

1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰

2：这个格子没有烈焰，且其左右两个格子中均有烈焰

$*$：这个格子有烈焰

?：未告诉你本格情况

solution

$f[i][0/1][0/1]$表示前i位，当前位和下一位是（1）不是（0）烈焰的方案数

转移方程分情况讨论：

当$s[i]=’*’$时：

$f[i][1][0]=(f[i-1][0][1]+f[i-1][1][1])$

$f[i][1][1]=(f[i-1][0][1]+f[i-1][1][1])$

当$s[i]=’0’$时，上一位、当前位和下一位都得是0：

$f[i][0][0]=f[i-1][0][0]$

当s[i]=’1’时，上一位或下一位有一个是1：

$f[i][0][1]=f[i-1][0][0]$

$f[i][0][0]=f[i-1][1][0]$

当s[i]=’2’时，上一位和下一位都是1当前位是0：

$f[i][0][1]=f[i-1][1][0]$

当s[i]=’?’时：

$f[i][1][0]=(f[i-1][0][1]+f[i-1][1][1])$

$f[i][1][1]=(f[i-1][0][1]+f[i-1][1][1])$

$f[i][0][0]=(f[i-1][0][0]+f[i-1][1][0])$

$f[i][0][1]=(f[i-1][0][0]+f[i-1][1][0])$

初值$f[0][0][0] =1,f[0][0][1] = 1$

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int dp[N][2][2];
char s[N];
int main() {
  cin >> s + 1;
  dp[0][0][0] = dp[0][0][1] = 1;
  int len = strlen(s + 1);
  for (int i = 1; i <= len; i++) {
    if (s[i] == '0')
      dp[i][0][0] = dp[i - 1][0][0];
    else if (s[i] == '1') {
      dp[i][0][0] = dp[i - 1][1][0];
      dp[i][0][1] = dp[i - 1][0][0];
    } else if (s[i] == '2')
      dp[i][0][1] = dp[i - 1][1][0];
    else if (s[i] == '*') {
      dp[i][1][0] = (dp[i - 1][1][1] + dp[i - 1][0][1]) % mod;
      dp[i][1][1] = dp[i][1][0];
    } else {
      dp[i][0][0] = (dp[i - 1][1][0] + dp[i - 1][0][0]) % mod;
      dp[i][0][1] = dp[i][0][0];
      dp[i][1][0] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % mod;
      dp[i][1][1] = dp[i][1][0];
    }
  }
  cout << (dp[len][1][0] + dp[len][0][0]) % mod << '\n';
  return 0;
}