1093 Count PAT‘s

题目描述
知识点： 解法一：状态机模型、DP 解法二：递增三元组、前缀和
思路：
解法一：我们使用f[i][j]表示利用前i个字母，得到状态j的方案数为多少。

状态指的是，当前匹配到哪个字母了，总共有4种状态:空、‘P’、‘A’、‘T’。

对于第i个字母，总共有两种选择，即不匹配第j个状态和匹配第j个状态。
如果不匹配第j个状态，则f[i][j]=f[i-1][j]
如果匹配第j个状态，则要满足第j个状态字符与第i个字母相同，
即f[i][j]=f[i-1][j-1] if(s[i]=p[j])
答案就是f[n][3]
此种解法适用于匹配多个字符的情况。

#include
#include
using namespace std;
const int N = 1e5+10,P = 1000000007;
int f[N][4];
char p[] = {' ','P','A','T'},s[N];
int main()
{
    cin>>s+1;
    int n = strlen(s+1);//从下标1开始统计长度
    f[0][0] = 1;
    for(int i = 1;i <= n;i++){
        for(int j = 0;j < 4;j++)
        {
            f[i][j] = f[i-1][j];
            if(s[i] == p[j])
                f[i][j] = (f[i][j] + f[i-1][j-1])%P;
        }
    }
    cout<<f[n][3];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

解法二：我们可以将’P’ ‘A’ 'T’三个字母出现的下标位置都用数组来存起来。
每个下标位置都可以有一组配对 只要里面的元素满足递增关系。这就是经典的递增三元组问题。
假设三个数组a b c。只要枚举中间的数组b，左边a数组只要找到比当前这个数小的元素个数，右边c数组只要找到比当前这个数大的元素个数。
递增三元组可以使用前缀和进行O(n)求解。
定义cnt[i]表示数组i出现的次数，则sum[i]表示前1~i元素出现的个数。
则左边比当前元素小的个数为sum[i-1] (假设i为当前的元素值)
右边比当前元素大的个数为sum[n]-sum[i] (n为总共最大的元素值)

#include
using namespace std;
const int N = 1e5+10,P=1000000007;
string s;
int p[N],a[N],t[N];
int sum_p[N],sum_a[N],sum_t[N];
int ans;
int main(){
    cin>>s;
    for(int i = 0;i < s.length();i++){
        if(s[i] == 'P')
           p[i+1]++;  
        else if(s[i] == 'A')
            a[i+1]++;
        else if(s[i] == 'T')
            t[i+1]++;
    }
    for(int i = 1;i < N;i++){
        sum_p[i] += sum_p[i-1] + p[i];
        sum_a[i] += sum_a[i-1] + a[i];
        sum_t[i] += sum_t[i-1] + t[i];
    }
    for(int i = 1;i < N;i++){
        if(a[i] >= 1){
            int left_p = sum_p[i-1];
            int right_t = sum_t[N-1]-sum_t[i];
            ans = (ans + (long long)left_p * right_t)%P;
        }
    }
    cout<<ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32