【斐波那契DP】HDU 4639——HeHe
HDU DP 斐波 那契
2023-09-27 14:22:40 时间
题目:点击打开链接
多校练习赛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; }
相关文章
- 致初学者(三): HDU 2033~ 2043题解
- HDU 1253:胜利大逃亡(简单三维BFS)
- HDU 4407 Sum
- HDU 4359 Easy Tree DP?
- HDU 2242 考研路茫茫——空调教室
- HDU 3397 Sequence operation
- HDU 3074 Multiply game
- HDU 4756 Install Air Conditioning
- HDU 6778 Car (状压DP)
- HDU 4632 Palindrome subsequence (区间DP)
- HDU 5956 The Elder (树上斜率DP)
- HDU 6156 Palindrome Function (数位DP)
- HDU 2829 Lawrence (斜率优化DP或四边形不等式优化DP)
- HDU 4405 Aeroplane chess (期望DP)
- HDU 5024 Wang Xifeng's Little Plot (DP)
- HDU 4352 XHXJ's LIS (数位DP+LIS+状态压缩)
- HDU 5898 odd-even number (数位DP)
- HDU 3664 Permutation Counting (DP)
- HDU 4462 Scaring the Birds (暴力求解,二进制法)
- HDU 3687 National Day Parade (暴力)
- HDU 3362 Fix (状压DP)
- HDU 1272 小希的迷宫
- hdu 5411 CRB and Puzzle (矩阵高速幂优化dp)
- hdu 4412 Sky Soldiers(区间DP)
- 多校第六场 HDU 4927 JAVA大数类+模拟
- HDU - 4734 F(x) (2013成都网络游戏,数字DP)
- hdu 1506 Largest Rectangle in a Histogram ((dp求最大子矩阵))
- hdu 1556 Color the ball (树状数组)