题解 | #abb#
abb
http://www.nowcoder.com/practice/0a8bbf8b9b5b4280957849ef4f240f07
描述
给一个长度为的字符串,问有多少个形式为abb的子序列
思路
-
一个比较常见的动态规划题目,设表示区间中以字母为结尾,有多少个形式为ab的子序列,则对于字符串最终的答案为,同时,,为区间中字母出现的次数。
-
由于更新仅和的各个状态相关,因此可以边循环变,可以省略一维存储空间
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
int cnt[30];
ll dp[MAXN];
char s[MAXN];
int main()
{
int n;
scanf("%d",&n);
scanf("%s",s+1);
ll sum=0;
for(int i=1;i<=n;i++)
{
int& num=cnt[s[i]-'a'];
int tot=i-1-num;
sum+=dp[s[i]-'a'];
dp[s[i]-'a']+=tot;
num++;
}
printf("%lld\n",sum);
}
时间复杂度,空间复杂度