河池市住房与城市建设部网站每平每家设计家官网

✨题目链接：

DP36 abb

✨题目描述 

leafee 最近爱上了 abb 型语句，比如“叠词词”、“恶心心”

leafee 拿到了一个只含有小写字母的字符串，她想知道有多少个 "abb" 型的子序列？
定义： abb 型字符串满足以下条件：

1. 字符串长度为 3 。
2. 字符串后两位相同。
3. 字符串前两位不同。

✨输入描述:

第一行一个正整数 𝑛n

第二行一个长度为 𝑛n 的字符串（只包含小写字母）

1≤𝑛≤1051≤n≤105

✨输出描述:

"abb" 型的子序列个数。 

✨示例1

📍输入

6 abcbcc

📍输出

8

📍说明

共有1个abb，3个acc，4个bcc 

✨解题思路

 动态规划：

1. 初始化计数器和数组：

   • f[26]：用来记录每个字母对结果的当前贡献。
   • g[26]：用来记录每个字母的出现次数。
   • res：结果变量，用来存储符合条件的子序列个数。
   • i：用来记录当前遍历到的字符的索引。

2. 遍历字符串：

   • 对于字符串中的每一个字符e：
     1. 将当前字符对结果的贡献加到res中。
     2. 更新字符e的贡献值：f[e-'a'] = f[e-'a'] + i - g[e-'a']。
        • i代表当前字符之前的所有字符数。
        • g[e-'a']是当前字符e之前出现的所有字符e的次数。
        • 通过计算i - g[e-'a']，得到当前字符e之前所有非e字符的数量。
     3. 更新字符e的出现次数：g[e-'a'] += 1。
     4. 增加遍历索引i。

 贡献值可以理解为在这以前区间有多少个    _ x   （假设现在 i 位置字符为x） 

✨代码
 

#include <iostream>
using namespace std;int main() {int n;cin >> n;string str;cin >> str;long long res = 0;int f[26]={0};int g[26]={0};long long i=0;for(auto e:str){res+=f[e-'a'];f[e-'a']=f[e-'a']+i-g[e-'a'];g[e-'a']=g[e-'a']+1;i++;}cout << res << endl;return 0;
}

---

※ 如果文章对你有帮助的话，可以点赞收藏！！谢谢支持