【1093】Count PAT‘s (25分)【递推】

1.题目

https://pintia.cn/problem-sets/994805342720868352/problems/994805373582557184
找出诸如APPAPT中包含多少个PAT（注意不是指“连续”）。

2.思路

若直接暴力解会超时！！
可以先算出T的个数（一层for），然后再一次for从左至右统计P和T的个数，而在这层for循环内的最后，遇到A的时候就可以计算结果：因为遍历字符串的每个A，该A前面的P的个数和该A后面的T的个数的乘积即能构成的PAT的个数，在这个for遍历累加result即可。

3.代码

#include<cstdio>
#include<stdlib.h>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
int main(){
	string s;
	cin>>s;
	int len=s.length(),result=0,countp=0,countt=0;
	for(int i=0;i<len;i++){//此处灰常巧妙
		if(s[i]=='T')
			countt++;
	}
	for(int i=0;i<len;i++){
		if(s[i]=='P') countp++;
		if(s[i]=='T') countt--;
		if(s[i]=='A') result=(result+(countp*countt)%1000000007)%1000000007;
	}
	cout<<result;
	system("pause");
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/112415996