洛谷 Hellow World（水题题解）

常规
1

P2246 SAC#1 - Hello World（升级版）题解

大致意思：

就是在一串字母中找出 HelloWorld 子序列出现的次数。

大致思路：

  • 暴力，跟据每个字母的位置及相同字母的位置，进行枚举和判断，时间 O (n) 。

  • 动态规划，因为题目提供的模板串长度比较小，所以我们可以将它存入数组，一位一位枚举。而我们知道因为是子序列，前面的情况也要包含进去，所以第 i 项需要加上 i - 1 项，因此得出公式 dp_{i} = dp_{i} + dp_{i - 1} ，时间复杂度依然为 O (n) 。

这道题我选择了第二种方法来做。

代码实现：

#include<bits/stdc++.h>
using namespace std;
int dp[20];
char s,c[20]={"helloworld"};
const long long mod=1000000007;
int main(){
    dp[0]=1;
	while(1){
		s=getchar();
		if(s==EOF){
			cout<<dp[10]<<endl;
			return 0;
		}
		char k=s+32;
		for(int i=9;i>=0;i--){
			if(k==c[i]||s==c[i]){
				dp[i+1]=(dp[i]+dp[i+1])%mod;
			}
		}
	}
	return 0;
}

这样这道题就完成啦！！！

博客网址

3 个赞