/* 解题方法： 动态规划--多态问题 shy:由y+sh组成 sh:由h+s组成 求s有多少 s[i]:表示[0, i]区间有多少个 sh[i]:表示[0,i]区间有多少个 shy[i]:表示[0,i]区间有多少个shy */ #include <iostream> (30316)#include <string> #include <vector> using namespace std; int main() { long long n; cin >> n; string str; cin >> str; //1.创建dp表 vector<long long> s(n + 1); auto h = s; auto y = h; //2.填表 for (int i = 1;i <= n;i++) { //求s s[i] = str[i - 1] == 's' ? s[i - 1] + 1 : s[i - 1]; //求sh h[i] = str[i - 1] == 'h' ? h[i - 1] + s[i - 1] : h[i - 1]; //求shy y[i] = str[i - 1] == 'y' ? y[i - 1] + h[i - 1] : y[i - 1]; //cout<<s[i]<<" "<<h[i]<<" "<<y[i]<<endl; } cout << y[n] << endl; } // 64 位输出请用 printf("%lld")