C3-I 子序列个数

题目描述

给出一个长度为 nn 的仅包含小写英文字母的字符串 ss，数一数 ss 有多少个子序列为 buaa。

形式化的，你需要统计以下四元组的数量：(a,b,c,d)(a,b,c,d) 满足 1≤a<b<c<d≤n1≤a<b<c<d≤n 且 sas_a= b，sbs_b= u，scs_c=sds_d= a。

输入

一行一个字符串表示 ss，保证 1≤n≤1051≤n≤10^5。

输出

一行一个整数表示答案。

题目分析

用一个二维数组dp[i][j]dp[i][j]表示ss的前ii个字符中以tt的前jj个字符作为子序列的个数，答案即为dp[lenS][4]dp[lenS][4]。

dp[0][0]=1,dp[i][0]=1,dp[0][j]=0dp[0][0]=1,dp[i][0]=1,dp[0][j]=0

当s[i−1]==t[j−1]s[i-1]==t[j-1]时有两种情况：

  • 不考虑s[i−1]s[i-1]此时对应dp[i−1][j]dp[i-1][j]
  • 考虑s[i−1]s[i-1]此时对应dp[i−1][j−1]dp[i-1][j-1]

当s[i−1]≠t[i−1]s[i-1]\not=t[i-1]时对应dp[i][j]=dp[i−1][j]dp[i][j]=dp[i-1][j]

示例代码

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
#include<stdio.h>
#include<string.h>
char s[100010];
long long dp[100010][4];
int main()
{
    char t[5]="buaa";
   	scanf("%s",s);
    int n=strlen(s);
    for(int i=0;i<n;i++)
    {
        dp[i][0]=1;
        for(int j=0;j<4;j++)
        {
            if(s[i]==t[j])
            {
				dp[i+1][j+1]=dp[i][j+1]+dp[i][j];
            }
            else
            {
                dp[i+1][j+1]=dp[i][j+1];
            }
        }
	}
    printf("%lld\n",dp[n][4]);
}