牛客小白月赛19「火」皇家烈焰(简单线性dp)

$非常水的一道题$

发现第$i$个位置与第$i-1$和$i+1$有关

所以直接暴力思维$dp$带着所有状态冲就是了

定义$dp[i][j][q][w]$为$dp$到第$i$位时

$i-1$位是否有火$(j)$,$i$位置是否有火$(q)$,$i+1$位置是否有火$(w)$

#include <bits/stdc++.h> using namespace std; #define int long long const int maxn=1e6+10; const int mod=1e9+7; int n,m,dp[maxn][2][2][2]; char a[maxn]; signed main() { cin >> (a+1); n=strlen(a+1); dp[0][0][0][0]=dp[0][0][0][1]=1; for(int i=1;i<=n;i++) { if( a[i]=='0' ) dp[i][0][0][0]=dp[i-1][1][0][0]+dp[i-1][0][0][0]; else if( a[i]=='1' ) { dp[i][0][0][1]=dp[i-1][1][0][0]+dp[i-1][0][0][0]; dp[i][1][0][0]=dp[i-1][1][1][0]+dp[i-1][0][1][0]; } else if( a[i]=='2' ) dp[i][1][0][1]=dp[i-1][1][1][0]+dp[i-1][0][1][0]; else if( a[i]=='*' ) { for(int j=0;j<=1;j++) for(int q=0;q<=1;q++) dp[i][j][1][q]=dp[i-1][0][j][1]+dp[i-1][1][j][1]; } else { for(int j=0;j<=1;j++) for(int q=0;q<=1;q++) for(int w=0;w<=1;w++) dp[i][j][q][w]=dp[i-1][0][j][q]+dp[i-1][1][j][q]; } for(int j=0;j<=1;j++) for(int q=0;q<=1;q++) for(int w=0;w<=1;w++) dp[i][j][q][w]%=mod; } int ans=0; for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) ans = (ans+dp[n][i][j][0] )%mod; cout << ans; }

但是似乎可以优化掉一维

因为转移的时候$i-1$是用不到的

在转移状态$i$时,只需要$i-1$的起火状态和$i$的起火状态

实际上只需要$dp[i][q][w]$即可