统计问题
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6525 Accepted Submission(s): 3843链接:
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
题意: 中文题目,题意就摆在这,我就不说啦~~~
分析:
这个题目比赛的时候我没想什么递推关系,非常明显。数据不大。我全然能够打表啊,其实,我这个题确实是dfs打表过的,1A,得到FB。然后赛后查看打表数据,我才发现递推关系 _zZ。
//打表代码int vis[50][60];void DFS(int x, int y, int step){ if(step == N) { ans++; return; } if(!vis[x - 1][y]) { vis[x - 1][y] = 1; DFS(x - 1, y, step + 1) ; vis[x - 1][y] = 0; } if(!vis[x][y - 1]) { vis[x][y - 1] = 1; DFS(x, y - 1, step + 1); vis[x][y - 1] = 0; } if(!vis[x][y + 1]) { vis[x][y + 1] = 1; DFS(x, y + 1, step + 1); vis[x][y + 1] = 0; }}
/****************************>>>>HEADFILES<<<<****************************/#include通过比对数据,发现ans[i] = ans[i-1]*2 + ans[i-2] ..... haha#include