「火」皇家烈焰

字符串的长度为n
对于30%的数据，n≤20
对于60%的的数据，n≤1,000
对于100%的数据，n≤1,000,000

直接枚举全部情况，对问好与特殊位置进行选择，计数，30分做法。

三维线性dp，100分做法。
通过三维数组dp[N][2][2]，0代表没有，1代表有烈焰，dp[i][j][k]代表当前在第i个位置，状态是j，后一个位置状态是k。
为什么不需要四维，因为当前位置前一个格子的状态，可以通过dp[i-1][j][k]去确定，i-1的j就是当前位置的前一个位置状态。
首先处理第一个位置的符号情况，后面通过第一个位置转移即可。

0：dp[0][0][0] = 1; 当前位置和后面都没用烈焰
1：dp[0][0][1] = 1; 当前位置没有第一个格子有烈焰
2：直接特判不合法，因为0没有前驱格子。
*：dp[0][1][0] = dp[0][1][1] = 1; 自己是烈焰，当前位置看后面有烈焰与没有烈焰都是合法。
？: for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) dp[0][i][j] = 1; 所有情况均合法

那么后面通过前面状态进行转移

0：dp[i][0][0] = dp[i-1][0][0]; 前一个位置没有烈焰后一个格子和自己也没有烈焰
1：dp[i][0][0] = dp[i - 1][1][0]; 前面位置是烈焰，后面和自己不是
1：dp[i][0][1] = dp[i - 1][0][0]; 前面位置和自己不是，后面是
2：dp[i][0][1] = dp[i - 1][1][0]; 前面是后面是，自己不是
*：dp[i][1][0] = dp[i][1][1] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD; 包含前面是烈焰与不是烈焰的情况，后面都可行。
？：dp[i][0][0] = dp[i][0][1] = (dp[i - 1][0][0] + dp[i - 1][1][0]) % MOD; 自己不是烈焰，后面都可行，那就是前一个格子后面不是烈焰的情况累加求和
？：dp[i][1][0] = dp[i][1][1] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD; 自己是烈焰，后面都可行，那就是前一个格子后面是烈焰的情况求和
最终状态dp[len-1][0][0]+dp[len-1][1][0]当前位置可能有烈焰也可能没有烈焰后面不存在后继一定是0，直接求和即可。

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

typedef long long ll;
const int  N = 1e6 + 5;
const int MOD = 1e9 + 7;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

ll dp[N][2][2];
char s[N];

int main() {
    scanf("%s", s); //也可以 %s -> s+1 初始化dp[0][0][0]=[0][0][1]=1就不用特判第一个位置了
    int len = strlen(s);
    if (s[0] == '0')
        dp[0][0][0] = 1;
    else if (s[0] == '1')
        dp[0][0][1] = 1;
    else if (s[0] == '2') {
        puts("0");
        return 0;
    }
    else if (s[0] == '*')
        dp[0][1][0] = dp[0][1][1] = 1;
    else if (s[0] == '?')
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                dp[0][i][j] = 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] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
        else if (s[i] == '?') {
            dp[i][0][0] = dp[i][0][1] = (dp[i - 1][0][0] + dp[i - 1][1][0]) % MOD;
            dp[i][1][0] = dp[i][1][1] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
        }
    }
    printf("%lld\n", (dp[len - 1][0][0] + dp[len - 1][1][0]) % MOD);
    return 0;
}

【每日一题】5月7日「火」皇家烈焰

「火」皇家烈焰