喵喵喵

第一篇较正经的题解

原题传送门

看完题了，思路很容易就有了

我们先找每次可走的范围（虚假的答案）

n=0

    0

n=1

        1
      1 0 1

n=2
       2
     2 1 2
   2 1 0 1 2

n=3
         3
       3 2 3
     3 2 1 2 3 
   3 2 1 0 1 2 3 

...

至此

规律已经呼之欲出

每一次的可走范围就是在上一次的范围上再套一层n

那么有人要说了：

“哇哇哇这肯定就是答案了吧”

（你猜我为什么有过一次wa 0的记录）

其实不然

我们来看这个例子

0 0 0
0 0 0

我们要从右下角到左上角

那么他可以有

3 0 0
2 1 0

1种

3 2 0
0 1 0

2种

3 2 1
0 0 0

3种

所以我们要去在上面枚举的范围上去找每个点的方案和

n=0
    0

$f(0)=1$

n=1
  1
1 0 1

$f(1)=3$

n=2
       1
     2 0 2
   1 0 0 0 1

$f(2)=7=1+6=1+2*3=f(0)+2*f(1)$

n=3
         1
       3 0 3
     3 0 2 0 3 
   1 0 0 0 0 0 1 

$f(3)=17=3+14=3+2*7=f(1)+2*f(2)$

...

至此

规律已经呼之欲出(*2)

$f(x)=f(x-2)+2*f(x-1)$

所以，我想说的是...

递推，启动！

#include<iostream>
using namespace std;
int n;
long long a[21];
int main(){
	cin>>n;
	a[0]=1; 
	a[1]=3;
	for(int i=2;i<=20;i++){
		a[i]=a[i-2]+2*a[i-1];
	}
	cout<<a[n];
	return 0;
}