笔试训练48天：mari和shiny（动态规划 - 线性dp）

链接：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; }