HDU 5907 Find Q dp

题目链接：这里 题意：问你有多少个子串，全部只含有q这个字母。 解法：直接dp就好了,dp[i]表示以i结尾的方案数，最后对dp累加求和就是答案。

//HDU 5907 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+7; int n; long long dp[maxn]; int main(){ int t; scanf("%d", &t); while(t--){ string s; cin >> s; memset(dp, 0, sizeof(dp)); for(int i = 0; i < (int)s.size(); i++){ if(s[i] == 'q') dp[i] = dp[i-1] + 1; } long long ans = 0; for(int i = 0; i < (int)s.size(); i++){ ans += dp[i]; } printf("%lld\n", ans); } return 0; }