mine(一道dp)题
这道题就是个dp
dp[i][j]表示正要推这个位置,这个位置字符是j时,使字符串合法的方案数。
0对应这个位置字符是0;
1对应这个位置字符是1;
2对应这个位置字符是2;
3对应这个位置字符是*;
这个位置字符是0,1,2,*时,是什么,j就更新什么,
这个位置字符是?,要讨论当这个位置是以上所有情况时。
再考虑怎么转移就行了。
//我的第三维,只在当j = 1时用到dp[i][1][0]表示这个位置是1,当个位置没放*。
dp[i][1][1]表示这个位置是1,当个位置放了*。
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
char s[1000005];
long long dp[1000005][4][2];
int main()
{
scanf("%s",s);
int len = strlen(s);
dp[0][1][0] = 1;
dp[0][0][0] = 1;
dp[0][2][1] = 0;
dp[0][3][0] = 0;
dp[0][1][1] = 0;
for(int i = 1; i <= len; i++)
{
if(s[i-1] == '?')
{
dp[i][3][0] = (dp[i][3][0] +dp[i-1][2][1]) % mod;
dp[i][3][0] = (dp[i][3][0] +dp[i-1][1][0]) % mod;
dp[i][3][0] = (dp[i][3][0] +dp[i-1][3][0]) % mod;
dp[i][2][1] = (dp[i][2][1] +dp[i-1][3][0]) % mod;
dp[i][1][0] = (dp[i][1][0] + dp[i-1][0][0])%mod;
dp[i][1][0] = (dp[i][1][0] + dp[i-1][1][1])%mod;
dp[i][1][1] = (dp[i][1][1] + dp[i-1][3][0])%mod;
dp[i][0][0] = (dp[i][0][0] + dp[i-1][0][0])%mod;
dp[i][0][0] = (dp[i][0][0] + dp[i-1][1][1])%mod;
}
if(s[i-1] == '1')
{
dp[i][1][0] = (dp[i][1][0] + dp[i-1][1][1])%mod;
dp[i][1][0] = (dp[i][1][0] + dp[i-1][0][0])%mod;
dp[i][1][1] = (dp[i][1][1] + dp[i-1][3][0])%mod;
}
if(s[i-1] == '2')
{
dp[i][2][1] = (dp[i][2][1] +dp[i-1][3][0]) % mod;
}
if(s[i-1] == '0')
{ dp[i][0][0] = (dp[i][0][0] + dp[i-1][0][0])%mod;
dp[i][0][0] = (dp[i][0][0] + dp[i-1][1][1])%mod;
}
if(s[i-1] == '*')
{
dp[i][3][0] = (dp[i][3][0] +dp[i-1][2][1]) % mod;
dp[i][3][0] = (dp[i][3][0] +dp[i-1][1][0]) % mod;
dp[i][3][0] = (dp[i][3][0] +dp[i-1][3][0]) % mod;
}
}
long long ans = 0;
ans = (dp[len][0][0] + dp[len][3][0] + dp[len][1][1]) % mod;
cout << ans;
return 0;
}