首页 > ACM题库 > HDU-杭电 > HDU 4639-Hehe-动态规划-[解题报告]HOJ
2015
09-17

HDU 4639-Hehe-动态规划-[解题报告]HOJ

Hehe

问题描述 :

As we all know, Fat Brother likes MeiZi every much, he always find some topic to talk with her. But as Fat Brother is so low profile that no one knows he is a rich-two-generation expect the author, MeiZi always rejects him by typing “hehe” (wqnmlgb). You have to believe that there is still some idealized person just like Fat Brother. They think that the meaning of “hehe” is just “hehe”, such like “hihi”, “haha” and so on. But indeed sometimes “hehe” may really means “hehe”. Now you are given a sentence, every “hehe” in this sentence can replace by “wqnmlgb” or just “hehe”, please calculate that how many different meaning of this sentence may be. Note that “wqnmlgb” means “我去年买了个表” in Chinese.

输入:

The first line contains only one integer T, which is the number of test cases.Each test case contains a string means the given sentence. Note that the given sentence just consists of lowercase letters.
T<=100
The length of each sentence <= 10086

输出:

The first line contains only one integer T, which is the number of test cases.Each test case contains a string means the given sentence. Note that the given sentence just consists of lowercase letters.
T<=100
The length of each sentence <= 10086

样例输入:

4
wanshangniyoukongme
womenyiqichuqukanxingxingba
bulehehewohaiyoushi
eheheheh

样例输出:

Case 1: 1
Case 2: 1
Case 3: 2
Case 4: 3

题目:点击打开链接

多校练习赛4的简单题,但是比赛的时候想到了推导公式f(n)=f(n-1)+f(n-2)(就是斐波那契数列),最后却没做出来。

首先手写一下he(不是hehe)连续时的规律。0-1 1-1 2-2 3-3 4-5,斐波那契无误。

比赛的时候没有分清楚连续的he和间断的he的不同,只有连续的he才能用斐波那契数列来表示,而间断点应该重新计算he出现的次数,最后根据组合数的原理相乘,即可得到最终的答案。

  

//dp,但是找规律也可以发现连续的是FIb数列. 
#include <iostream>
#include <cstring>
using namespace std;

long long tar[10100];

void create_fib()
{
	tar[0]=1;
	tar[1]=1;
	for(int i=2;i<=10086;i++)
	{
		tar[i]=tar[i-1]+tar[i-2];
		tar[i]%=10007;
	}
}

int main()
{
	int testcase;
	string str;
	create_fib();
	cin>>testcase;
	for(int t=1;t<=testcase;t++)
	{
		int answer=1,count=0;
		cin>>str;
		for(int i=0;i<str.length();)
		{
			if(str[i]=='h' && str[i+1]=='e')
			{
				count++;
				i+=2;
			}
			else
			{
				answer*=tar[count];
				answer%=10007;
				count=0;
				i++;
			}
		}
		answer*=tar[count]; //最后一段要乘上
		answer%=10007;
		
		cout<<"Case "<<t<<": "<<answer<<endl;
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/mig_davidli/article/details/9730799


  1. 拉倒吧,反对派对毛衣的威胁要比is大,至少对普特勒是如此。杀人放火不算啥,思想犯最严重,因为它动摇自己的统治根基,对全世界的土匪都一样

  2. 拉倒吧,反对派对毛衣的威胁要比is大,至少对普特勒是如此。杀人放火不算啥,思想犯最严重,因为它动摇自己的统治根基,对全世界的土匪都一样

  3. 拉倒吧,反对派对毛衣的威胁要比is大,至少对普特勒是如此。杀人放火不算啥,思想犯最严重,因为它动摇自己的统治根基,对全世界的土匪都一样

  4. 拉倒吧,反对派对毛衣的威胁要比is大,至少对普特勒是如此。杀人放火不算啥,思想犯最严重,因为它动摇自己的统治根基,对全世界的土匪都一样

  5. 拉倒吧,反对派对毛衣的威胁要比is大,至少对普特勒是如此。杀人放火不算啥,思想犯最严重,因为它动摇自己的统治根基,对全世界的土匪都一样

  6. 拉倒吧,反对派对毛衣的威胁要比is大,至少对普特勒是如此。杀人放火不算啥,思想犯最严重,因为它动摇自己的统治根基,对全世界的土匪都一样

  7. 拉倒吧,反对派对毛衣的威胁要比is大,至少对普特勒是如此。杀人放火不算啥,思想犯最严重,因为它动摇自己的统治根基,对全世界的土匪都一样

  8. 拉倒吧,反对派对毛衣的威胁要比is大,至少对普特勒是如此。杀人放火不算啥,思想犯最严重,因为它动摇自己的统治根基,对全世界的土匪都一样

  9. 拉倒吧,反对派对毛衣的威胁要比is大,至少对普特勒是如此。杀人放火不算啥,思想犯最严重,因为它动摇自己的统治根基,对全世界的土匪都一样