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

「火」皇家烈焰

https://ac.nowcoder.com/acm/problem/53683

题目

题目描述：
帕秋莉掌握了一种火属性魔法
由于钟爱扫雷游戏，帕秋莉把自己图书馆前的走廊看作一个一维的扫雷地图，她制造了很多烈焰，排在这条走廊内
现在帕秋莉告诉你一部分烈焰的分布情况，请你告诉她可能的情况有多少种
对于一个格子，里面会有以下几种字符：
0：这个格子没有烈焰，且其左右两个格子均没有烈焰
1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰
2：这个格子没有烈焰，且其左右两个格子中均有烈焰
*：这个格子有烈焰
？：未告诉你本格情况

输入描述：

一个字符串

输出描述：
输出一行，一个整数表示答案，对1e9+7取模

解析

梳理题目意思，这就是一个一维扫雷。

这道题很清楚的可以看出来是一道dp，而且这么多情况还要分类讨论

所以还是先这个：动态规划最重要的就是递推。

动态规划：

这道题我相信大家一下就能看出来这是一个dp的题目。但是我却想不到该用一个什么样的dp。
我重复了很多遍的递推固然重要，但是我有一点没提过：就是dp数组的意义。
这道题我完全没有数组定义的思路，在看了邓老师的题解之后我感觉有了一些发现：数组应该根据所求数据的相关性进行确定。
本道题我们将dp数组定义为：dp[i][0/1][0/1]。（dp[下标位置][本位是否为烈焰][下一位是否为烈焰] = 到达下标位置之前的种类数）
那么本憨憨就会问了！这dp凭啥这样定义啊！：因为我们在某个位置上有没有火焰，单纯与上一位，本位和下一位有关。上一位可以在转移的体现，所以如此定义。

算法操作：

既然我们已经有了dp数组，这道题就简单很多了：我们分为四种情况进行递推，并写出转移方程。

本位为0的情况：自己不是火焰，两边也都不应该有火焰。

dp[i][0][0] = dp[i - 1][0][0] % MOD;
//左式表示当前位和下一位均不为0，右式表示上一位和当前位均不为0（以下递推式均以此类推）
//因为两侧都必须为0，所以只有这一种情况

本位为1的情况：自己不是火焰，左右又一边是火焰。

dp[i][0][0] = dp[i - 1][1][0] % MOD;
//判定左边为火焰的情况：三个位置分别为1,0,0
dp[i][0][1] = dp[i - 1][0][0] % MOD;
//判定右边为火焰的情况：三个位置分别为0,0,1

本位为2的情况：自己不是火焰，左右都是火焰。

dp[i][0][1] = dp[i - 1][1][0] % MOD;
//因为两边都有火焰，所以只有一种情况：分别为1,0,1

本位为*的情况：自己是火焰，左右不知道（因为假如是数字就是表示这里有，不是数字也可以是？和*_{（连续雷嘛）}，所以最多只知道不能是0）。

dp[i][1][0] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
//自己是火焰，假设后面不是，前面不能确定，所以两种情况可以加起来
dp[i][1][1] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
//自己是火焰，假设后面也是，前面依旧不能确定，所以也是两种情况加起来

本位为?的情况：自己是啥不知道，左右是啥也不知道（所以这就包含了所有的可能性）。

dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][1][0]) % MOD;
dp[i][0][1] = (dp[i - 1][0][0] + dp[i - 1][1][0]) % MOD;
//假设本位不是是火焰，再讨论下一位
dp[i][1][0] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
dp[i][1][1] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
//假设本位是火焰，再讨论下一位

那么这些我们都知道了之后呢，我们还有一个很重要的东西：特殊条件。
我们的递推要考虑到前一位和后一位是什么，这就导致首尾比较特殊：首位没有上一位，尾位没有下一位。
所以我们将首尾都设置为0，防止影响到操作。
然后我们是从前往后递推的，所以我们就要初始化起始值：
```
dp[0][0][0] = dp[0][0][1] = 1;
```
我们是以首位的上一位为本位，所以在此位为0的时候，他的下一位无论是什么都是一种情况。

那么，打代码：

先输入我们的字符串，这里因为dp数组的首位特判，我们舍弃字符串的0位（方便编程）。
然后分类讨论进行递推（详情看上面）。
看代码吧~~~

AC代码

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
#define IOS ios::sync_with_stdio(false);
//代码预处理区

const int MOD = 1e9 + 7;
const int MAX = 1e6 + 7;
int dp[MAX][2][2];
//全局变量区

//函数预定义区

int main() {
    IOS;
    string s; cin >> s;
    s = " " + s;
    memset(dp, 0, sizeof dp);
    dp[0][0][0] = dp[0][0][1] = 1;
    int lens = s.length();
    for (int i = 1; i < lens; i++)
        if ('0' == s[i])
            dp[i][0][0] = dp[i - 1][0][0] % MOD;
        else if ('1' == s[i]) {
            dp[i][0][0] = dp[i - 1][1][0] % MOD;
            dp[i][0][1] = dp[i - 1][0][0] % MOD;
        }
        else if ('2' == s[i])
            dp[i][0][1] = dp[i - 1][1][0] % MOD;
        else if ('*' == s[i]) {
            dp[i][1][0] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
            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 - 1][0][0] + dp[i - 1][1][0]) % MOD;
            dp[i][0][1] = (dp[i - 1][0][0] + dp[i - 1][1][0]) % MOD;
            dp[i][1][0] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
            dp[i][1][1] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
        }
    cout << (dp[lens - 1][0][0] + dp[lens - 1][1][0]) % MOD << endl;
    return 0;
}
//函数区

每日一题文章被收录于专栏

憨憨的专栏