【HDU-2044】解题报告（递推，水题）

原始题目

一只小蜜蜂...

  • Time Limit: 2000/1000 MS (Java/Others)
  • Memory Limit: 65536/32768 K (Java/Others)
  • Total Submission(s): 93384
  • Accepted Submission(s): 33247

Problem Description

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。 其中，蜂房的结构如下所示。

1.jpg
1.jpg

Input

输入数据的第一行是一个整数N,表示测试实例的个数，然后是N 行数据，每行包含两个整数a和b(0<a<b<50)。

Output

对于每个测试实例，请输出蜜蜂从蜂房a爬到蜂房b的可能路线数，每个实例的输出占一行。

Sample Input

2
1 2
3 6

Sample Output

1
3

Author

lcy

Source

递推求解专题练习（For Beginner）

Recommend

lcy

题目大意

如题

解题思路

递推，dp初步，\(dp[i]=dp[i-1]+dp[i-2]\)

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
#define eps 1e-8
#define INF 0x3f3f3f3f
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
using namespace std;
const int maxn=1e5+5;
typedef long long ll;

ll dp[100][100];
int main(){
	ll t;
	memset(dp,0,sizeof(dp));
		dp[0][0]=dp[1][1]=0;

		for(ll i=1;i<=50-1;i++){
			for(ll j=1;j<=50;j++){
				if(i==j)dp[i][j]=0;
				else if(j==i+1) dp[i][j]=1;
				else if(j==i+2) dp[i][j]=2;
				else dp[i][j]=dp[i][j-1]+dp[i][j-2];
//				cout<<i<<" "<<j<<endl;
			}
		} 
	while(cin>>t){
		ll a,b;
		rep(i,0,t){
		
		cin>>a>>b;
			cout<<dp[a][b]<<endl;
		}
		
	}
}

收获与反思

没啥