文章目錄

• • 題目分析
  • 題目鏈接

題目分析

來源：acwing

分析：統(tǒng)計(jì)子串“PAT”的數(shù)量。

狀態(tài)機(jī)模型：本題需要的是PAT，需要選3個(gè)字母，對(duì)應(yīng)三條邊，需要4個(gè)狀態(tài)。

下面以樣例來說明一下狀態(tài)機(jī)是怎么轉(zhuǎn)移的。首先看到第一個(gè)字母，到達(dá)這里是狀態(tài)0，發(fā)現(xiàn)它是字母A，我們第一個(gè)轉(zhuǎn)移需要的是字母P，所以狀態(tài)還是0，然后到達(dá)下一個(gè)字母，就是狀態(tài)0，發(fā)現(xiàn)這個(gè)字母是P，P是第一個(gè)可以用的字母，這時(shí)候觸發(fā)了狀態(tài)0到狀態(tài)1 的轉(zhuǎn)移機(jī)制，此時(shí)有兩種選擇（如下圖兩種狀態(tài)）：選擇轉(zhuǎn)移，或者不轉(zhuǎn)移。轉(zhuǎn)移的話就是狀態(tài)1，不轉(zhuǎn)移的話還是狀態(tài)0.

選擇轉(zhuǎn)移（下圖中數(shù)字代表狀態(tài)）：這時(shí)候到了第二個(gè)字母P下面，狀態(tài)改為1，此時(shí)需要的是A，然后繼續(xù)到達(dá)下一個(gè)字母，此時(shí)狀態(tài)是1，到達(dá)之后，發(fā)現(xiàn)是A，這里又觸發(fā)了狀態(tài)1到狀態(tài)2的轉(zhuǎn)移機(jī)制，可以選擇轉(zhuǎn)移或者不轉(zhuǎn)移，此處只能轉(zhuǎn)移，（只有1個(gè)A不轉(zhuǎn)移的話就湊不出PAT啦），因此到達(dá)下一個(gè)字母的時(shí)候狀態(tài)變成2，發(fā)現(xiàn)是字母P沒用，接著到下一個(gè)字母，狀態(tài)還是2，發(fā)現(xiàn)這個(gè)字母是T，觸發(fā)狀態(tài)2到狀態(tài)3的轉(zhuǎn)移，再往后走，雖然沒有數(shù)字了，但是仍然要轉(zhuǎn)移，狀態(tài)記為3.只有到達(dá)狀態(tài)3，才說明找到一種合法的方案。

選擇不轉(zhuǎn)移（下圖中數(shù)字代表狀態(tài)）：這時(shí)候到了第二個(gè)字母P下面，狀態(tài)還是0，發(fā)現(xiàn)是可以用的P，觸發(fā)轉(zhuǎn)移機(jī)制，可以選轉(zhuǎn)移或者不轉(zhuǎn)移，這里選擇轉(zhuǎn)移，那么到達(dá)下一個(gè)字母的時(shí)候狀態(tài)變?yōu)?，此時(shí)發(fā)現(xiàn)這個(gè)字母是A，出發(fā)轉(zhuǎn)移機(jī)制，這里選擇轉(zhuǎn)移，到達(dá)下一個(gè)字母的狀態(tài)變成2，此時(shí)發(fā)現(xiàn)字母是P，不轉(zhuǎn)移，到達(dá)下個(gè)字母的狀態(tài)還是2，然后發(fā)現(xiàn)該字母是T，觸發(fā)轉(zhuǎn)移機(jī)制，這里選擇轉(zhuǎn)移，到下一個(gè)位置狀態(tài)變成3，表示一種合法方案。如下圖。

知道了狀態(tài)機(jī)大概是什么樣子，我們開始dp的狀態(tài)機(jī)分析

狀態(tài)表示：$f[i][j]$表示只考慮前i個(gè)字母，且走到了狀態(tài)j的所有路線的數(shù)量。所以我們要求的答案就是$f[n][3]$,這里n是給的字符串的長度，3是最終的狀態(tài)（如上圖中的狀態(tài)3）.

狀態(tài)計(jì)算：

ac代碼

#include<bits/stdc++.h> using namespace std;const int N =1e5+10 , mod =1000000007 ;char s[N],p[] =" PAT"; //下標(biāo)從1開始 int n; int f[N][4]; int main(){cin >> s+1; //從下標(biāo)1開始讀n = strlen(s+1); //長度f[0][0] = 1; //初始化，為的是狀態(tài)機(jī)能夠運(yùn)轉(zhuǎn)起來，f[1][0] = f[0][0] =1for(int i =1; i<= n; i++) //枚舉每個(gè)字符for(int j =0; j<=3; j++){ //枚舉每個(gè)狀態(tài)f[i][j]= f[i-1][j]; //不選第i個(gè)字符//選第i個(gè)字符，前提是滿足條件if(s[i] == p[j]) f[i][j] = (f[i][j] + f[i-1][j-1]) % mod;}//最終答案就是 考慮前n個(gè)字符，且狀態(tài)是3的路線的數(shù)量cout << f[n][3] <<endl; }

題目鏈接

PAT甲級(jí)1093 Count PAT’s
https://www.acwing.com/problem/content/1585/

總結(jié)

以上是生活随笔為你收集整理的PAT甲级1093 Count PAT‘s ：[C++题解]DP、状态机模型dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。