暴力解决
#include <iostream>
using namespace std;
int main() {
string s;
cin >> s;
int sz = s.size();
int res = 0;
for(int i = 0;i<sz;i++) {
for(int j = i + 1;j<sz;j++) {
for(int k = j + 1;k<sz;k++) {
if(s[i] == 'Q' && s[j]=='A' && s[k] == 'Q'){
res++;
}
}
}
}
cout << res << endl;
}
dp
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
string s; // 声明一个字符串s用来存储输入
cin >> s; // 读入字符串
int n = s.size(); // n为字符串s的长度
// 创建一个大小为n的_vector,初始值都为0,用来存储当前位置前面有多少个"QA"子序列
vector<int> dp(n, 0);
for (int i = 1; i < n; ++i) { // 从第二个字符开始遍历字符串
dp[i] = dp[i - 1]; // 首先将dp[i]设为dp[i-1],即假设当前字符并不增加"QA"子序列的数量
if (s[i] == 'A') { // 判断当前字符是否为'A'
// 如果当前字符是'A',则从头遍历到当前字符,统计'Q'的数量
for (int j = 0; j < i; ++j) {
if (s[j] == 'Q') {
dp[i]++; // 如果字符是'Q',则dp[i]加1
}
}
}
}
int res = 0; // 初始化结果为0
// 从第三个字符开始遍历字符串
for (int i = 2; i < n; ++i) {
if (s[i] == 'Q') { // 如果当前字符是'Q'
res += dp[i - 1]; // 在结果res中加上当前位置前面的"QA"子序列数量
}
}
cout << res << endl; // 输出结果
return 0;
}