1040. 有几个PAT（25）

字符串APPAPT中包含了两个单词“PAT”，其中第一个PAT是第2位(P),第4位(A),第6位(T)；第二个PAT是第3位(P),第4位(A),第6位(T)。

现给定字符串，问一共可以形成多少个PAT？

输入格式：

输入只有一行，包含一个字符串，长度不超过10⁵，只包含P、A、T三种字母。

输出格式：

在一行中输出给定字符串中包含多少个PAT。由于结果可能比较大，只输出对1000000007取余数的结果。

输入样例： APPAPT 输出样例： 2

思路：dp[i][0]表示前i位有几个P，dp[i][1]表示前i位有几个PA，dp[i][2]表示前i位有几个PAT。

#include <iostream> #include <stdio.h> #include <stdlib.h> #include<string.h> #include<algorithm> #include<math.h> #include<queue> using namespace std; typedef long long ll; char a[100010]; const ll mod=1e9+7; ll dp[100010][3]={{0}}; int main() { cin>>a; int l=strlen(a); ll ans=0; if(a[0]=='P') dp[0][0]=1; for(int i=1;i<l;i++) { if(a[i]=='P') { dp[i][0]=(dp[i-1][0]+1)%mod; dp[i][2]=dp[i-1][2]; dp[i][1]=dp[i-1][1]; } else if(a[i]=='A') { dp[i][0]=dp[i-1][0]; dp[i][1]=(dp[i-1][1]+dp[i-1][0])%mod; dp[i][2]=dp[i-1][2]; } else { dp[i][0]=dp[i-1][0]; dp[i][1]=dp[i-1][1]; dp[i][2]=(dp[i-1][2]+dp[i-1][1])%mod; } } cout<<dp[l-1][2]<<endl; return 0; }