商丘购物网站开发设计,网站建设题目,室内设计师培训班多少钱,建设网站视频百度云盘链接#xff1a; 「火」皇家烈焰 文章目录题目描述题解#xff1a;代码#xff1a;时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K
64bit IO Format: %lld题目描述 帕秋莉掌握了一种火属性魔法 由于钟爱扫…链接 「火」皇家烈焰
文章目录题目描述题解代码时间限制C/C 1秒其他语言2秒
空间限制C/C 262144K其他语言524288K
64bit IO Format: %lld题目描述 帕秋莉掌握了一种火属性魔法 由于钟爱扫雷游戏帕秋莉把自己图书馆前的走廊看作一个一维的扫雷地图她制造了很多烈焰排在这条走廊内 现在帕秋莉告诉你一部分烈焰的分布情况请你告诉她可能的情况有多少种 对于一个格子里面会有以下几种字符 0这个格子没有烈焰且其左右两个格子均没有烈焰 1这个格子没有烈焰且其左右两个格子中只有一个烈焰 2这个格子没有烈焰且其左右两个格子中均有烈焰 *这个格子有烈焰 未告诉你本格情况 输入描述: 一个字符串 输出描述: 输出一行一个整数表示答案对1e97取模 示例1 输入
?1?输出
2说明 已知第二个格子左右有一个烈焰
因此可能的情况有10和01显然其他情况都无法满足已知条件的要求 备注: 字符串的长度为n 对于30%的数据n≤20 对于60%的的数据n≤1,000 对于100%的数据n≤1,000,000
题解
乍一看以为是扫雷。仔细一看为什么又是dp每日一题好爱出dp而我dp又是渣渣
在其他大佬那吸取知识之后写出自己的理解
我们仔细看题可以看出每个点什么情况其实都与两侧的点息息相关我可以通过一个点算出两侧点的状态也可以根据两侧状态来反推中间的点。 但是我们状态转移的顺序是从左到右我们在转移过程中考虑第i点时i-1之前的点状态都是固定的所以我们只需要考虑当前点i与之后一个点i1的状态。 在第i点时i1可能也有了要求所以不满足情况的就不用转移状态。 dp[i][0/1/2/3]
0表示i与i1都不是火 1表示i是火i1不是火 2表示i不是火i1是 3表示i和i1都是火
对照题目给出的状态 0这个格子没有烈焰且其左右两个格子均没有烈焰1这个格子没有烈焰且其左右两个格子中只有一个烈焰2这个格子没有烈焰且其左右两个格子中均有烈焰*这个格子有烈焰未告诉你本格情况具体情况如下
ifi 0) 说明i-1ii1都没有火,i 的状态就是等同于i-1的状态都是0即本身与右边都不是火 转移方程f [i ] [ 0 ] f [ i - 1 ] [ 0 ]
ifi 1 i不是火但是i的周围有一个火 如果左边是火,那么右边就不是火那i就满足状态0i-1就满足状态1f[i][0]f[i-1][1] 如果右边是火左边就不是火那么i就满足状态2i-1就满足状态0f [ i ][ 2 ] f [ i - 1 ] [ 0]
ifi 2 左右均为火那么i-1是火i不是火i1是火i就满足状态2: f [ i ] [ 2 ] f [ i-1 ] [ 1 ]
ifi * 当前i为火I1有两种情况 一个是i1位火 f [ i ] [ 3 ] f [ i - 1 ] [ 2 ] f [ i - 1 ] [ 3 ] i1不是火 f [ i ] [ 1 ] f [ i - 1 ] [ 2 ] f [ i - 1 ] [ 3 ]
ifi ? 当前点未知我们就要考虑所有情况 i为火i不为火i1为火i1不为火 四种情况 i与i1都不是火 f [ i ] [0 ] f[ i - 1 ][ 0 ] f [i - 1 ] [ 1 ]
i不是i1是火 f [ i ] [ 2 ] f [ i - 1 ] [ 0 ] f [ i - 1 ] [ 1 ]
i是火i1不是 f [ i ] [ 1 ] f [ i - 1 ] [ 2 ] f [i - 1 ] [ 3 ]
i和i1都是火 f [ i ] [ 3 ] f [ i - 1 ] [ 2 ] f [ i - 1 ][ 3 ]
到最后一个点ii后面没有点了相当于i1不是火 答案就是 i是火与不是火了两种情况加一起 f [ i ] [ 0 ] f [ i ] [ 1 ] 此时i地图长度
对了前往不要忘了取模mod
结合我讲的在代码里面一条一条对应
代码
#includebits/stdc.h
using namespace std;
const int maxn1e61,mod1e97;
int f[maxn][7];
char s[maxn];
int main()
{f[0][0]f[0][2]1; cins;int lenstrlen(s);for(int i1;ilen;i){if(s[i-1]0){f[i][0]f[i-1][0];}else if(s[i-1]1){f[i][0]f[i-1][1];f[i][2]f[i-1][0];}else if(s[i-1]2){f[i][2]f[i-1][1];}else if(s[i-1]*){f[i][1](f[i-1][2]f[i-1][3])%mod;f[i][3](f[i-1][2]f[i-1][3])%mod;}else if(s[i-1]?){f[i][0](f[i-1][0]f[i-1][1])%mod;f[i][2](f[i-1][0]f[i-1][1])%mod;f[i][1](f[i-1][2]f[i-1][3])%mod;f[i][3](f[i-1][2]f[i-1][3])%mod;}}cout(f[len][0]f[len][1])%mod;return 0;
}
