16届蓝桥杯寒假刷题营】第2期DAY5IOI赛
3.小蓝小彬的代码挑战 - 蓝桥云课
问题描述
在蓝桥杯大赛中，小蓝和小彤是一对好朋友。他们在比赛中遇到了一个有趣的挑战。这个挑战是给定一个由大写字母组成的代码，他们需要找出这串代码中有多少个子序列LQB。小蓝和小彬都很聪明，他们想到了一个巧妙的方法，但是他们还是需要你的帮助。请你帮助他们完成这个挑战。
输入格式
第一行包含一个字符串S（1≤|S|≤10⁵）。其中，|S|表示S的字符数。S只包含大写字母。
输出格式
输出一个整数，表示S中子序列LQB的数量。
样例输入
LQQLBQB样例输出
6思路：
很常见的dp思路，记录每一段子数列出现的次数。类似递推
代码如下：
#include <iostream>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
ll dp[4];
int main()
{
string s;
cin >> s;
for(ll i = 0 ; i < s.size() ; i++)
{
if(s[i] == 'L')
{
dp[1]++;
}
if(s[i] == 'Q')
{
dp[2] += dp[1];
}
if(s[i] == 'B')
{
dp[3] += dp[2];
}
}
cout << dp[3];
return 0;
}