Hdoj 2563.统计问题 题解

Problem Description

在一无限大的二维平面中，我们做如下假设：
1、 每次只能移动一格；
2、 不能向后走（假设你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）；
3、 走过的格子立即塌陷无法再走第二次；
求走n步不同的方案数（2种走法只要有一步不一样，即被认为是不同的方案）。

Input

首先给出一个正整数C，表示有C组测试数据
接下来的C行，每行包含一个整数n (n<=20)，表示要走n步。

Output

请编程输出走n步的不同方案总数；
每组的输出占一行。

Sample Input

2
1
2

Sample Output

3
7

Author

yifenfei

Source

绍兴托普信息技术职业技术学院——第二届电脑文化节程序设计竞赛

---

思路

将问题进行分割，(f[n])表示走了n步后的方案数，将其表示为(f[n] = up[n] + lr[n])

显然有：

• (up[n] = up[n-1]+lr[n-1])，向上只有1个方向
• (lr[n] = 2*up[n-1] + lr[n-1])，如果本来是向上走，那么就可以向左或者向右；如果本来是向左或向右就只能继续前进

最后有：

递推式：(f[i] = 2 * f[i-1] + f[i-2])

初始条件：(f[1] = 3, f[2] = 7)

代码

#include<bits/stdc++.h>
using namespace std;
__int64 f[21];
int main()
{
	int t;
	
	f[1] = 3; f[2] = 7;
	for(int i=3;i<=20;i++)
		f[i] = 2 * f[i-1] + f[i-2]; 
	
	cin >> t;
	while(t--)
	{
		int tmp;
		cin >> tmp; 
		cout << f[tmp] << endl;
	}
	return 0;	
}