每日OJ题_牛客_mari和shiny_线性dp_C++_Java

目录

牛客_mari和shiny_线性dp

题目解析

C++代码

Java代码

牛客_mari和shiny_线性dp

mari和shiny (nowcoder.com)

描述：
        mari每天都非常shiny。她的目标是把正能量传达到世界的每个角落！
有一天，她得到了一个仅由小写字母组成的字符串。
她想知道，这个字符串有多少个"shy"的子序列？
（所谓子序列的含义见样例说明）

题目解析

C++代码

#include <iostream>
#include <string>
using namespace std;int main()
{int n = 0;string str;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;
}

Java代码

import java.util.*;
public class Main
{public static void main(String[] args){Scanner in = new Scanner(System.in);int n = in.nextInt();char[] str = in.next().toCharArray();long s = 0, h = 0, y = 0;for(int i = 0; i < n; i++){char ch = str[i];if(ch == 's'){s += 1;}else if(ch == 'h'){h += s;}else if(ch == 'y'){y += h;}}System.out.println(y);}
}