当前位置：首页 > article >正文

牛客习题—线性DP 【mari和shiny】C++

article 2024/10/19 0:23:53

你好，欢迎阅读我的文章~

个人主页：@Mike

所属专栏：动态规划

mari和shiny

分析:

使用动态规划的思路来解决。

思路：

分别统计s，sh，shy的数量即可。使用ss来统计字符s的数量，使用sh来统计字符sh的数量，使用shy来统计字符shy的数量。

代码实现：

十年OI一场空，不开longlong见祖宗。

#include<stdlib.h>
#include<iostream>
using namespace std;
#define int long long


signed main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int ss=0;
    int sh=0;
    int shy=0;
    
    for(int i=0;i<n;i++)
    {
        if(s[i]=='s')
        {
            ss++;
        }
        else if(s[i]=='h')
        {
            sh=sh+ss;
        }
        else if(s[i]=='y')
        {
            shy=shy+sh;
        }
    }
    
    cout<<shy<<endl;
    
}