【每日一题】「火」皇家烈焰 题解

Solution

根据题目给的限制关系, 很容易就联想到线性的动态规划
令 表示第 位是当前位有/无火的方案数 (这里我的 代表无火, 代表有火)
但是这道题对 的限制范围不止来自 , 还来自
因此无法二维表示这种状态关系的转移
考虑多加一维, 令 表示第 位当前有/无火, 后一位() 有无火
而 的限制可以由 来表示, 这样我们就找到了状态转移方程

好多, 累死我，其实就是根据题意很显然的就能列出来了
转移方程的具体含义我在代码注释里写出来了, 很好理解
这道题的难点在于如何表示状态, 一旦找到状态表示方法
只要根据题意做转移就行了
最后的答案就是
即最后一个位置有火的方案数加上最后一个位置没有火的方案数
注意不要忘了一开始的初始化

Code

/*
  autor: Kurisu
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const long long inf = 1e18;
const int N = 1e6 + 5;
const double eps = 1e-10;
const ll mod = 1e9 + 7;
ll dp[N][2][2];
int main() {
  string s;
  cin >> s;
  s = " " + s;
  int n = s.size() - 1;
  dp[0][0][0] = dp[0][0][1] = 1;
  for(int i = 1; i <= n; i++) {
    if(s[i] == '0') { // 当前和左右都无
      dp[i][0][0] += dp[i - 1][0][0], dp[i][0][0] %= mod;
    }
    else if(s[i] == '1') { // 当前无 左右 有一个
      dp[i][0][0] += dp[i - 1][1][0]; dp[i][0][0] %= mod; // 左有
      dp[i][0][1] += dp[i - 1][0][0], dp[i][0][1] %= mod; // 右有
    }
    else if(s[i] == '2') { // 当前无 左右均有
      dp[i][0][1] += dp[i - 1][1][1], dp[i][0][1] %= mod; // 左右有
    }
    else if(s[i] == '*') { // 当前有 左右任意
      dp[i][1][0] += (dp[i - 1][0][1] + dp[i - 1][1][1]), dp[i][1][0] %= mod; // 当前有 右无 然后 左有或者没有
      dp[i][1][1] += (dp[i - 1][0][1] + dp[i - 1][1][1]), dp[i][1][1] %= mod; // 当前有 右有 然后 左有或者没有
    }
    else if(s[i] == '?') { // 当前任意
      dp[i][1][0] += (dp[i - 1][0][1] + dp[i - 1][1][1]), dp[i][1][0] %= mod; // 当前为火 右无
      dp[i][1][1] += (dp[i - 1][0][1] + dp[i - 1][1][1]), dp[i][1][1] %= mod; // 当前和右 为火
      dp[i][0][1] += (dp[i - 1][0][0] + dp[i - 1][1][0]), dp[i][0][1] %= mod; // 当前无 右火
      dp[i][0][0] += (dp[i - 1][0][0] + dp[i - 1][1][0]), dp[i][0][0] %= mod; // 当前无 右无
    }
  }
  cout << (dp[n][1][0] + dp[n][0][0]) % mod << "\n"; // 最后一格有 和 无的方案
  return 0;
}