状态机DP
$O(n)$
分析本题,可以发现每个合法的字符串PAT
必然能被拆分成三个状态:P
,PA
,PAT
,同时这三个状态之间是有联系的,也就是只有PA
仅能由状态P
推出来,状态PAT
仅能由状态PA
推出来,这进而联想到用状态机DP来做(状态机模型的若干连线方式)。
故设 P —— 0,PA —— 1,PAT —— 2,这样对应了三个状态。
f[i][j]表示前i个字符中,状态为j的字符串的数量。
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10,mod = 1000000007;
char s[N];
int f[N][3];
//f[i][j]:前i个字符串中状态为j的情况出现次数
// 0:P ,1:PA,2:PAT
int main()
{
cin >> s + 1;
int n = strlen(s + 1);
for(int i = 1;i <= n;i ++ )
{
if(s[i] == 'P')
{
f[i][0] = (f[i - 1][0] + 1) % mod;
f[i][1] = f[i - 1][1];
f[i][2] = f[i - 1][2];
}
if(s[i] == 'A')
{
f[i][0] = f[i - 1][0];
//f[i - 1][0]是针对第i个位置出现了‘A’,所以它前面所有出现过的
//P都可以和它组成PA
f[i][1] = (f[i - 1][0] + f[i - 1][1]) % mod;
f[i][2] = f[i - 1][2];
}
if(s[i] == 'T')
{
f[i][0] = f[i - 1][0];
f[i][1] = f[i - 1][1];
f[i][2] = (f[i - 1][2] + f[i - 1][1]) % mod;
}
}
cout << f[n][2];
return 0;
}