題目鏈接：點擊查看

題目大意：給出一個長度為 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)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。