1196四角い格子を踏む-プッシュ方法!

何度も何度も何度も何度も何度も何度も何度も何度も何度も何度も何度も何度も何度も何度も何度も何度も何度も何度も何度も何度も何度も何度も何度も何度も
とても楽しくて、手動で滑稽で、手動で犬の頭を使います
タイトル:
 
1196:四角い格子を踏む
時間制限:1000 msメモリ制限:65536 KBコミット数:2857パス数:1893
【タイトル説明】
行列の境界が無限遠にある格子行列がある.次のように仮定します.
a、一歩歩くたびに、現在のグリッドから1格だけ移動して、隣接するグリッドに行くことができます.
b、歩いた格子はすぐに陥没して二度と歩けない.
c、北、東、西の3つの方向にしか歩けない.
すみません、四角行列の上でn歩を歩くことを許可すれば、何種類の異なる案がありますか.2つの歩き方は、一歩でも異なるものがあれば、異なる案とされています.
【入力】
四角い格子の上を歩くことができる歩数n(n≦20).
【出力】
計算されたシナリオの数.
【入力サンプル】

2

【出力サンプル】

7

【出所】
No
統計の送信
 
この問題について使うプッシュ式については、焦らずに下にひっくり返して、私と一緒に考えてください.
一歩しか歩けないときは、左、前、右の3つの歩き方があります.(順番が大事)
2つのステップを歩くと、分類して議論します.
1、第一歩は左へ:左と前へしか行けない
2、第一歩前へ進む:三つの方向に進むことができる
3、一歩下がって右へ行く:右へ行くか前へ行くしかない
だから全部で7種類の歩き方があります.
左へ行く方法数と右へ行く方法数は同じで,前へ行く方法数だけが異なることが分かった(複数)
/*左へ:今は2つの選択肢に直面しています:今は3つの選択肢に直面しています*/
左へ行くことと右へ行くことを左へ行くことに統合すると、次のようになります.
n=1の場合:左へ=1,前へ=1,方法数:左へ*2+前へ(最初は左(2種)か前(3種)か)
n=2の場合、左へ=3、前へ=1、方法数:左へ*2+前へ
n=3のとき(自分で押す、複雑ではありません)、左へ=7、前へ=3の方法数:左へ*2+前へ
まとめ:
n=n+1の場合、左へ=nの場合は左へ*2+nの場合は前へ、前へ=nの場合は左へ.
コード:
 

#include 
using namespace std;
const int maxn=1e5+100;
int a[maxn];

int main()
{
	int n,i,m;
	cin>>n;
	long ans1=1;
	long ans2=1;
	long a=0;
	for(i=2; i<=n; i++)
	{
		a=ans2;
		ans2=ans1+ans2*2;
		ans1=a;
	}
	cout<