1093. Count PAT's

发表于 分类于 ， 阅读次数： 本文字数： 128 阅读时长 ≈ 1 分钟

#题意

计算PAT字串个数

#思路

动态规划?

增加一个PAT个数PA个数P个数
P不变不变增加1
A不变增加前面的P的个数不变
T增加前面的PA字串的个数不变不变

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

typedef long long ll;

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    ll p = 0, pa = 0, pat = 0;

    for (int i = 0; i < n; i++) {
        switch (s[i]) {
            case 'P': p++; break;
            case 'A': pa = (pa + p) % 1000000007; break;
            case 'T': pat = (pat + pa) % 1000000007; break;
        }
    }
    cout << pat % 1000000007 << endl;

    return 0;
}