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

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

大致意思：

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

大致思路：

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

• 动态规划，因为题目提供的模板串长度比较小，所以我们可以将它存入数组，一位一位枚举。而我们知道因为是子序列，前面的情况也要包含进去，所以第 $i$ 项需要加上 $i-1$ 项，因此得出公式 $d{p}_i=d{p}_i+d{p}_{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;
}

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