链接：https://ac.nowcoder.com/acm/problem/26226
来源：牛客网
题号：NC26226
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
题目描述
mari每天都非常shiny。她的目标是把正能量传达到世界的每个角落！
有一天，她得到了一个仅由小写字母组成的字符串。
她想知道，这个字符串有多少个"shy"的子序列？
（所谓子序列的含义见样例说明）
输入描述:
第一行一个正整数n，代表字符串的长度。（1≤n≤300000） 第二行为一个长度为n，仅由小写字母组成的字符串。
输出描述:
一个正整数，代表子序列"shy"的数量。
示例1
输入
8 sshhyyau
输出：
8
说明：假设字符串下标从1到8。共有（135）（136）（145）（146）（235）（236）（245）（246）八个"shy"子序列。
备注:mari大喊道：“是shiny不是shy！！！”
思路：动态规划
①：状态表示：s[i]表示:字符串str中[0,i]区间内有多少个's';
h[i]:表示[0,i]区间有多少个'sh';
y[i]:表示[0,i]区间有多少个'shy'
②状态转移方程:
③空间优化
#include <iostream> #include <string> using namespace std; int n; string str; int main() { cin>>n>>str; long long s=0,h=0,y=0; for(int i=0;i<n;i++) { char ch=str[i]; if(ch=='s')s++; else if (ch=='h')h+=s; else if(ch=='y')y+=h; } cout<<y<<endl; return 0; }
