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

「火」皇家烈焰

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

应该很容易看出是要用dp解决的,然后我开了个二维的dp[i][0/1]表示i号位置有没有火焰,结果好像发现情况分不太清楚。

题目大意:
直接看题目吧。

思路:
如果设置为dp[i][0/1]表示i号位置有无火焰的话,当前是1的时候,我们需要判断i+1位和i-1位的情况。但是由于dp从小到大,所以我无法判断i+1的情况了,于是我就做不下去了。
后来看了题解,发现有人用这个二维dp做的。居然直接去判断后面i+1位的情况。。。
居然还可以这样,哎,对dp的理解太浅了。

看了大部分的题解是,dp[i][0/1][0/1]表示第i个位置有无火焰并且第i+1个位置有无火焰的方案。
这样子的话,从上一个位置转移过来的时候,我们转移状态其实就可以搞清楚了。
具体见代码。这里初始化要让dp[0][0][0]=dp[0][0][1]=1

代码:

#include<bits/stdc++.h>
using namespace std;
char s[1000040];
const long long mod=1000000007;
long long f[1000400][2][2];
int main()
{
    cin>>s+1;
    int n=strlen(s+1);
    //cout<<n<<endl<<s+1<<endl;
    f[0][0][0]=1;f[0][0][1]=1;
    for(int i=1;i<=n;i++){
        if(s[i]=='*'){
            f[i][1][0]=(f[i-1][1][1]+f[i-1][0][1])%mod;
            f[i][1][1]=(f[i-1][1][1]+f[i-1][0][1])%mod;
        }
        if(s[i]=='0'){
            f[i][0][0]=f[i-1][0][0];
        }
        if(s[i]=='1'){
            f[i][0][0]=f[i-1][1][0];
            f[i][0][1]=f[i-1][0][0];
        }
        if(s[i]=='2'){
            f[i][0][1]=f[i-1][1][0];
        }
        if(s[i]=='?'){
            f[i][0][1]=(f[i-1][1][0]+f[i-1][0][0])%mod;
            f[i][0][0]=(f[i-1][1][0]+f[i-1][0][0])%mod;
            f[i][1][1]=(f[i-1][0][1]+f[i-1][1][1])%mod;
            f[i][1][0]=(f[i-1][0][1]+f[i-1][1][1])%mod;
        }
    }
    cout<<(f[n][0][0]+f[n][1][0])%mod<<endl;
    return 0;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-04 23:04
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议