鏈接：https://ac.nowcoder.com/acm/problem/15669
來源：牛客網
XHRlyb和她的小伙伴Cwbc在玩捉迷藏游戲，
Cwbc藏在多個不區分大小寫的字串中，
好奇的XHRlyb想知道，在每個字串中Cwbc作為子序列分別出現了多少次，
由于Cwbc可能出現的次數過多，你只需要輸出每個答案對2000120420010122取模后的結果，
聰明的你在仔細閱讀題目后，一定可以順利的解決這個問題！
輸入描述:
輸入資料有多行，每行有一個字串，
輸出描述:
輸出資料應有多行，每行表示一個答案取模后的結果，
示例1
輸入
復制
Cwbc
輸出
復制
1
說明
Cwbc作為子序列僅出現了1次，
示例2
輸入
復制
acdcecfwgwhwibjbkblcmcnco
輸出
復制
81
說明
Cwbc作為子序列出現了34=81次，
備注:
每行字串長度不超過2×105，字串總長度不超過106
經典的字串匹配子序列，我們用dp[i][j],表示前i個字符匹配了j個字符，
這里j序列有四個cwbc即dp[i][1],dp[i][2],dp[i][3],dp[i][4];
狀態轉換方程就是
我們考慮是子序列
假如我們要找的是cw，規模小一點，好模擬一點，
字串cwbwcw
dp[1]=1
第二個是w可與第一個c匹配
dp[2]=dp[2](原先的已經匹配好的+現在的w與前面的c能夠匹配多少個，
dp[i][1]=(dp[i][1]+s[i]‘c’) //s[i]'c’是個邏輯值，如果相同就是1，不同就是0；
dp[i][2]=(dp[i][2]+(s[i]‘w’)*dp[i-1][1]);
dp[i][3]=(dp[i][3]+(s[i]‘b’)*dp[i-1][2]);
dp[i][4]=(dp[i][4]+(s[i]‘c’)*dp[i-1][3]);
這一般來說就可以過了，但是資料太大，二維是不太行的，
考慮到當前狀態只與前一個狀態有關，
所有可以寫成
dp[1]=(dp[1]+(s[i]‘c’));
dp[2]=(dp[2]+(s[i]‘w’)*dp[1]);
dp[3]=(dp[3]+(s[i]‘b’)*dp[2]);
dp[4]=(dp[4]+(s[i]==‘c’)*dp[3]);
答案就是輸出dp[4]；
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=2000120420010122;
ll dp[5];
int main()
{ string s;
while(cin>>s)
{
for(int i=1;i<5;i++)
dp[i]=0;
for(int i=0;i<s.length();i++)
{
s[i]=tolower(s[i]);//轉換為小寫字符的函式
dp[1]=(dp[1]+(s[i]=='c'))%mod;
dp[2]=(dp[2]+((s[i]=='w')*dp[1]))%mod;
dp[3]=(dp[3]+((s[i]=='b')*dp[2]))%mod;
dp[4]=(dp[4]+((s[i]=='c')*dp[3]))%mod;
}
cout << dp[4]%mod<< endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/204180.html
標籤：其他
上一篇：2020淘寶雙11自動刷喵幣腳本