CodeForces - 1426F Number of Subsequences(dp)

题目链接：点击查看

题目大意：给出一个长度为 n 的字符串，由 ' a ' , ' b ' , ' c ' 和 ' ? ' 组成，每一个 ' ? ' 都可以变成三个字母之一，这样的话假设有 k 个 ' ? ' ，则整个字符串就有 3^k 中不同的表示，现在问这 3^k 个字符串中，一共有多少个 abc 的子序列（不需要连续）

题目分析：考虑 dp，如果没有 ' ? ' 的话还是比较经典的一道 dp 题目，dp[ i ][ 0 ] 代表的是到了第 i 个位置时， ' a ' 子序列的个数，dp[ i ][ 1 ] 代表的是到了第 i 个位置时，' ab ' 子序列的个数，dp[ i ][ 2 ] 代表的是到了第 i 个位置时，' abc ' 子序列的个数，答案显然就是 dp[ n ][ 2 ] 了

考虑 ' ? ' 会对 dp 的转移产生什么影响，因为 ' ? ' 可以将三种字母全部都表示一遍，所以到了第 i 个位置时，如果前面有 x 个 ' ? ' 的话，那么到达此位置的字符串就会有 3^x 种，如果不考虑 ' ? ' 的话，碰到一个 ' a ' ，dp[ i ][ 0 ] 就需要加一，但现在如果考虑到 ' ? ' 的影响，dp[ i ][ 0 ] 就需要加上 3^x 才行

再考虑用 ' ? ' 去分别表示三种字母：

' ? ' 表示 ' a ' ：前面仍然有 dp[ i - 1 ][ 0 ] 个 ' a '，仍然有 dp[ i - 1 ][ 1 ] 个 ' ab '，仍然有 dp[ i - 1 ][ 2 ] 个 ' abc '，多了 3^x 个 ' a '

' ? ' 表示 ' b ' ：前面仍然有 dp[ i - 1 ][ 0 ] 个 ' a '，仍然有 dp[ i - 1 ][ 1 ] 个 ' ab '，仍然有 dp[ i - 1 ][ 2 ] 个 ' abc '，多了 dp[ i - 1 ][ 0 ] 个 ' ab '

' ? ' 表示 ' c ' ：前面仍然有 dp[ i - 1 ][ 0 ] 个 ' a '，仍然有 dp[ i - 1 ][ 1 ] 个 ' ab '，仍然有 dp[ i - 1 ][ 2 ] 个 ' abc '，多了 dp[ i - 1 ][ 1 ] 个 ' abc '

直接转移就好了

代码：

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;const int mod=1e9+7;LL dp[N][3];char s[N];int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d%s",&n,s+1);LL base=1;for(int i=1;i<=n;i++){if(s[i]=='a'){dp[i][0]=(dp[i-1][0]+base)%mod;dp[i][1]=dp[i-1][1];dp[i][2]=dp[i-1][2];}else if(s[i]=='b'){dp[i][0]=dp[i-1][0];dp[i][1]=(dp[i-1][0]+dp[i-1][1])%mod;dp[i][2]=dp[i-1][2];}else if(s[i]=='c'){dp[i][0]=dp[i-1][0];dp[i][1]=dp[i-1][1];dp[i][2]=(dp[i-1][1]+dp[i-1][2])%mod;}else if(s[i]=='?'){dp[i][0]=(dp[i-1][0]*3+base)%mod;dp[i][1]=(dp[i-1][1]*3+dp[i-1][0])%mod;dp[i][2]=(dp[i-1][2]*3+dp[i-1][1])%mod;base=base*3%mod;}}printf("%lld\n",dp[n][2]);return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1426F Number of Subsequences(dp)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。