統(tǒng)計問題

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 833 Accepted Submission(s): 523

Problem Description 在一無限大的二維平面中，我們做如下假設(shè)： 1、??每次只能移動一格； 2、??不能向后走（假設(shè)你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）； 3、??走過的格子立即塌陷無法再走第二次； 求走n步不同的方案數(shù)（2種走法只要有一步不一樣，即被認為是不同的方案）。 ?

Input 首先給出一個正整數(shù)C，表示有C組測試數(shù)據(jù) 接下來的C行，每行包含一個整數(shù)n (n<=20)，表示要走n步。 ?

Output 請編程輸出走n步的不同方案總數(shù)； 每組的輸出占一行。 ?

Sample Input 2 1 2 ?

Sample Output 3 7 挑戰(zhàn)思維的一道題 假設(shè)處于第i步，設(shè)a[i]表示第i步向上走，b[i]表示第i步向左或右的步數(shù)，總步數(shù)f[i]=a[i]+b[i] 假設(shè)第i步上走，則其可以是第i-1步向上走再向上走得到即a[i-1]，也可以是第 i-1步往左或右走得到（因為向上走沒有什么限制）即b[i-1]，所以a[i]=a[i-1]+b[i-1]; 假設(shè)第i步向左或右走，則可以是第i-1步向上走再往左或右走得到，因為兩個方向都可以所以即為2*a[i-1]，也可以是 第i-1步往左之后只能再往左或往右之后只能再往右走得到（只能繼續(xù)保持原來的方向，所以不能乘以2），b[i]=2*a[i-1]+b[i-1];解這三個方程得f[n]=2*f[n-1]+f[n-2],,,, 解得時候要有點耐心，也不是很容易一下子看得出來的 #include<iostream> #include<cstdio> using namespace std; long long ?f[21]; int main() { ? ? int cas,n; ? ? f[1]=3;f[2]=7; ? ? for(int i=3;i<=20;i++) ? ? ? ? f[i]=2*f[i-1]+f[i-2]; ? ? cin>>cas; ? ? while(cas--) ? ? { ? ? ? ? cin>>n; ? ? ? ? cout<<f[n]<<endl; ? ? } ? ? return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/smilesundream/p/6642576.html

總結(jié)

以上是生活随笔為你收集整理的hdu 2563的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。