ps怎么做网站的广告条,wordpress 作品相册,页面设计标准,旅游网站设计与分析✨题目链接#xff1a;
DP36 abb ✨题目描述 leafee 最近爱上了 abb 型语句#xff0c;比如“叠词词”、“恶心心” leafee 拿到了一个只含有小写字母的字符串#xff0c;她想知道有多少个 abb 型的子序列#xff1f; 定义#xff1a; abb 型字符串满足以下…
✨题目链接
DP36 abb ✨题目描述 leafee 最近爱上了 abb 型语句比如“叠词词”、“恶心心” leafee 拿到了一个只含有小写字母的字符串她想知道有多少个 abb 型的子序列 定义 abb 型字符串满足以下条件 字符串长度为 3 。字符串后两位相同。字符串前两位不同。 ✨输入描述: 第一行一个正整数 n 第二行一个长度为 n 的字符串只包含小写字母 1≤≤1051≤n≤105 ✨输出描述: abb 型的子序列个数。 ✨示例1
输入 6 abcbcc 输出 8说明 共有1个abb3个acc4个bcc ✨解题思路 动态规划 初始化计数器和数组 f[26]用来记录每个字母对结果的当前贡献。g[26]用来记录每个字母的出现次数。res结果变量用来存储符合条件的子序列个数。i用来记录当前遍历到的字符的索引。 遍历字符串 对于字符串中的每一个字符e 将当前字符对结果的贡献加到res中。更新字符e的贡献值f[e-a] f[e-a] i - g[e-a]。 i代表当前字符之前的所有字符数。g[e-a]是当前字符e之前出现的所有字符e的次数。通过计算i - g[e-a]得到当前字符e之前所有非e字符的数量。更新字符e的出现次数g[e-a] 1。增加遍历索引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 i0;for(auto e:str){resf[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;
} ※ 如果文章对你有帮助的话可以点赞收藏谢谢支持
