皇家烈焰题解
「火」皇家烈焰
https://ac.nowcoder.com/acm/problem/53683
我感觉这题就是一个模拟,但是又要用到一个DP思想,因为dp无后效,其实就是每个情况讨论一下就好,,主要判断是否有雷无雷的情况,然后设计dp状态mdp[i][0/1];就是第i个无雷和有雷情况,这个大佬给了我很好的思路,主要模拟好就可以过。
我看大佬理解的 ,主要还是搞清楚自己模拟的是什么,就是分类讨论有无雷的各种情况。其实还是很简单
https://blog.nowcoder.net/n/ce7f2223a33b476ab952a80fac51d752大佬给我的启示
#include <bits/stdc++.h> #define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define debug(x) cout << #x << ": " << x << endl; #define debug1(x) cout<<"xxx"<<endl; #define ll long long #define ull unsigned long long #pragma GCC optimize("Ofast","inline","-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #define mse(a,b) memset(a,b,sizeof a); using namespace std; const int maxx=1e6+100; const int mod=1e9+7; int dp[10000100][2]; int main() { string s; cin>>s; int n=s.length(); s=" "+s; dp[0][0]=1; for(int i=1; i<=n; i++) { if(s[i]=='0') { dp[i][0]=dp[i-1][0]; } else if(s[i]=='2') { dp[i][0]=dp[i-1][1]; } else if(s[i]=='1') { if(s[i+1]=='*') { dp[i][0]=dp[i-1][0]; } else if(s[i+1]=='?') { dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod; } else { dp[i][0]=dp[i-1][1]; } } else if(s[i]=='*') { dp[i][1]=dp[i-1][0]+dp[i-1][1]; dp[i][1]%=mod; } else { if(s[i-1]=='0') { dp[i][0]=dp[i-1][0]; } else if(s[i-1]=='2') { dp[i][1]=dp[i-1][0]; } else if(s[i-1]=='1') { dp[i][1]=dp[i-2][0]; dp[i][0]=dp[i-2][1]; } else { dp[i][0]=dp[i][1]=(dp[i-1][0]+dp[i-1][1])%mod; } } } int ans=dp[n][1]+dp[n][0]; ans%=mod; printf("%d\n",ans); return 0; }