PTA A_1093 Count PAT's

798236606

题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805373582557184

解：递推法

1. #include <stdio.h>
   
2. #include <string.h>
   
3. 
   
4. typedef long long int LL;
   
5. 
   
6. char str[100010];
   
7. int P_num[100010];
   
8. int T_num[100010];
   
9. 
   
10. int main(void)
    
11. {
    
12.         int i, len;
    
13.         LL count = 0;
    
14.         
    
15.         gets(str);
    
16.         
    
17.         len = strlen(str);
    
18.         
    
19.         P_num[0] = (str[0] == 'P') ? 1 : 0;
    
20.         T_num[len - 1] = (str[len - 1] == 'T') ? 1 : 0;
    
21.         
    
22.         for (i = 1; i < len; i++)
    
23.                 P_num[i] = (str[i] == 'P') ? (P_num[i - 1] + 1) : P_num[i - 1];
    
24. 
    
25.         for (i = len - 2; i >= 0; i--)
    
26.                 T_num[i] = (str[i] == 'T') ? (T_num[i + 1] + 1) : T_num[i + 1];
    
27. 
    
28.         for (i = 0; i < len; i++)
    
29.                 if (str[i] == 'A')
    
30.                         count += (LL)P_num[i] * (LL)T_num[i];
    
31. 
    
32.         printf("%d", count % 1000000007);
    
33.         
    
34.         return 0;
    
35. }

复制代码