实在不会做看了各路大佬分享的题解，希望我记住了这种递推！

f = [0, 0, 2, 4, 12]
n = int(input())
for i in range(5, n+1):
    f.append(2*f[i-1]+2*f[i-2]-2*f[i-3]+f[i-4])

print(f[n])

/*****************
备注：
*****************/
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <set>
#include <queue>
#include <bitset>
#include <deque>
#include <stack>
#include <ctime>
using namespace std;
#define LL long long
#define MAXM 3010
#define MAXN 3010
const int N =1e5+10;
const int INF =0x3f3f3f3f;
int a[11],h,cnt=0; 
int main ()
{
    
    for(int i=1;i<=10;i++)
    {
        cin>>a[i];
    }
    cin>>h;
    for(int i=1;i<=10;i++)
    {
        if(a[i]<=h+30)
        {
            cnt++;
        }
    }
        
    cout<<cnt;  
   return 0;
}

#include<cstdio>
using namespace std;
struct arr{int n,p[1001];}g[1001],f[1001];
int n,i;
arr chen(arr a)
{
for (int i=1;i<=a.n;i++)
a.p[i]*=2;
for (int i=1;i<=a.n;i++)
if (a.p[i]>9) {a.p[i+1]+=a.p[i]/10;a.p[i]%=10;}
if (a.p[a.n+1]>0) a.n++;
return a;
}
arr add(arr a,arr b)
{
a.n=a.n>b.n?a.n:b.n;
for (int i=1;i<=a.n;i++)
a.p[i]+=b.p[i];
for (int i=1;i<=a.n;i++)
if (a.p[i]>9) {a.p[i+1]+=a.p[i]/10;a.p[i]%=10;}
if (a.p[a.n+1]>0) a.n++;
return a;
}
arr Minus(arr a,arr b)
{
int i=1,j,k;
while (i<=b.n)
{
if (a.p[i]>=b.p[i])a.p[i]=a.p[i]-b.p[i];
else
{
j=i+1;
while (a.p[j]==0) j++;
a.p[j]--;
for (k=i+1;k<j;k++) a.p[k]=9;
a.p[i]=a.p[i]+10-b.p[i];
}
i++;
}
while (a.p[a.n]==0&&a.n>1)a.n--;
return a;
}
int main()
{
//freopen("vans.in","r",stdin);
//freopen("vans.out","w",stdout);
scanf("%d",&n);
g[1].p[1]=2;g[2].p[1]=2;g[3].p[1]=8;
g[1].n=g[2].n=g[3].n=1;
f[1].p[1]=0;f[2].p[1]=2;f[3].p[1]=4;
f[1].n=f[2].n=f[3].n=1;
for (i=4;i<=n;i++)
{
g[i]=Minus(add(chen(f[i-1]),add(g[i-1],g[i-2])),g[i-3]);
f[i]=add(f[i-1],g[i-1]);
}
for (i=f[n].n;i>0;i--)
printf("%d",f[n].p[i]);
printf("\n");
}

(转载自http://billylinux.blog.hexun.com/10542440_d.html，感谢作者！）

这一题可以用DP解决：

考虑到要经过每一个点，那么对于最后形成的路，每一竖条横向的路不是4条就是2条，总共8种（不考虑路径方向）：

1 2 3 4 5 6 7 8

－ － － － －

－ － － － －

－ － － － －

－ － － － －

（7中最上面的与最下面的相连、8中最上面的与第二个相连）

并且对于经过最后面的4个点，路径形状只可能是两种（3、8），于是我们定义两个状态

a[i]——有i竖条，以3号形状结尾的路径数

b[i]——有i竖条，以8号形状结尾的路径数

例如：对于i=3：

a[3]=2 b[3]=2

接下来的问题，就是如何进行状态转移：

我们考虑下面的几种情况：

对于a[i]，它可以接在a、a……与b、b……上（这里的接上，指的是中间不出现3号与8号路径），并且除了a以外，其他都有两种接法（a有3种），因此经过分类，我们可以得到：

a[i]=2*(a+a+……+a[2]+b+b+……+b[2]+1)+a

而对于b[i],不难发现，他只能接在a与b上，因此有

b[i]=a+b

于是我们可以将a[i]化简为

a[i]=a+2+2*(b+b+……b[3])

至此问题大致解决，另外需要注意的是要用高精度。

推荐使用亿进制。

很巧妙的dp题。。。很难想，但超好编，枚举每列横向边的情况即可

注意 要高精度

1000位大整数魔鬼，可别说我耍赖皮，没有内存限制，吃掉了快5MB才AC
```cpp
#include <iostream>

using namespace std;

int l[1001][1000]={0};
//{0,0,2,4,12,0}
//l[i]=l[i-4]-l[i-3]*2+l[i-2]*2+l[i-1]*2
void outl(int n)
{
int i;
bool flag=false;
for(i=0;i<1000;i++)
{
if(l[n][i]!=0)
{
flag=true;
}
if(flag)
{
cout<<l[n][i];
}
}
//cout<<endl;
}

void add(int n)
{
int i,temp;
for(i=0;i<1000;i++)
{
l[n][i]=l[n-4][i]-(l[n-3][i]*2)+(l[n-2][i]*2)+(l[n-1][i]*2);
}
for(i=999;i>0;i--)
{

if(l[n][i]>=10)
{
temp=l[n][i]/10;
l[n][i]=l[n][i]%10;
l[n][i-1]+=temp;
}

/*
while(l[n][i]>10)
{
l[n][i]-=10;
l[n][i-1]++;
}
*/
while(l[n][i]<0)
{
l[n][i]+=10;
l[n][i-1]--;
}
}
}

int main()
{
l[0][999]=0;
l[1][999]=0;
l[2][999]=2;
l[3][999]=4;
l[4][999]=2;
l[4][998]=1;
int n,i;
cin>>n;
if(n>4)
{
for(i=5;i<=n;i++)
{
add(i);
}
}
outl(n);
return 0;
}

解题思路：

1）参考：http://www.docin.com/p-94253938.html

2）注意：递归的性能优化

3）注意：大整数的处理
可参考：http://blog.csdn.net/loophome/article/details/79322682

#include <vector>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
struct BigInt
{
    static const int Base = 100000000;
    static const int Width = 8;
    vector <int> s;
    BigInt (long long num = 0) 
    {
        *this = num;
    }
    BigInt operator = (long long num)
    {
        s.clear();
        do
        {
            s.push_back(num % Base);
            num /= Base;
        }while (num > 0);
        return *this;
    }
    BigInt operator + (const BigInt &b) const
    {
        BigInt res;
        res.s.clear();
        for (int i = 0, count = 0;;i++)
        {
            if (count == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = count;
            if (i < s.size()) x += s[i];
            if (i < b.s.size()) x += b.s[i];
            res.s.push_back(x % Base);
            count = x / Base;
        }
        return res;
    }
    
    BigInt operator - (const BigInt &b) const
    {
        BigInt res;
        res.s.clear();
        for (int i = 0, carry = 0;;i++)
        {
            if (carry == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = carry;
            carry = 0;
            if (i < s.size()) x += s[i]; else break;
            if (i < b.s.size()) x -= b.s[i];
            if (x < 0) 
            {
                carry = -1;
                x += Base;
            }
            res.s.push_back(x %Base);
        }
        return res;
    }
    friend  ostream& operator << (ostream &out, const BigInt& x)
    {
        out << x.s.back();
        for(int i = x.s.size()-2; i >= 0; i--)
        {
            char buf[20];
            sprintf(buf, "%08d", x.s[i]);
            for(int j = 0; j < strlen(buf); j++) out << buf[j];
        }
        return out;
    }
};

int main()
{
    int n;
    scanf("%d",&n);
    BigInt f[4]={0,0,1,2},g[4]={0,1,1,4};
    if (n < 4) cout << f[n] + f[n];
    else
    {
        for (int i = 4; i <=n; i++)
        {
            f[i%4] = f[(i-1)%4] + g[(i-1)%4];
            g[i%4] = f[(i-1)%4] + f[(i-1)%4] + g[(i-1)%4] +g[(i-2)%4] -g[(i-3)%4]; 
        }
        cout << f[n%4] + f[n%4];
    } 
    
    
}

递推式......太难了
#include <cstdio>
#include <cstring>

int n,f[1100][300]={{0},{1,0},{1,2},{1,4},{1,12}};

void addx(int a[],int b[]){
int c[300]={0};
int len=a[0]>b[0]?a[0]:b[0];
for(int i=1;i<=len;i++){
c[i]+=a[i]+b[i];
c[i+1]+=c[i]/10000;
c[i]%=10000;
}
len++;
while(c[len]==0&&len>1)
len--;
c[0]=len;
memcpy(a,c,sizeof(c));
}

void minusx(int a[],int b[]){
int c[300]={0};
int len=a[0];
for(int i=1;i<=len;i++){
c[i]+=a[i]-b[i];
if(c[i]<0){
c[i]+=10000;
c[i+1]-=1;
}
}
while(c[len]==0&&len>1)
len--;
c[0]=len;
memcpy(a,c,sizeof(c));
}

void Q(int a[]){
printf("%d",a[a[0]]);
for(int i=a[0]-1;i>=1;i--)
printf("%04d",a[i]);
}

int main(){
freopen("plan.in","r",stdin);
freopen("plan.out","w",stdout);
scanf("%d",&n);
if(n<=4){
printf("%d",f[n][1]);
return 0;
}
int t[300];
for(int i=5;i<=n;i++){
memcpy(f[i],f[i-4],sizeof(t));
addx(f[i],f[i-2]);
addx(f[i],f[i-2]);
addx(f[i],f[i-1]);
addx(f[i],f[i-1]);
minusx(f[i],f[i-3]);
minusx(f[i],f[i-3]);
}
Q(f[n]);
return 0;
}

原题[不是本题]的题解（2）：

Program vans;
function cf(x,y:integer):qword;
var i:integer;
begin
cf:=1; for i:=1 to y do cf:=cf*x;
end;
var n,m:integer;
begin
assign(input,'vans.in'); reset(input);
assign(output,'vans.out'); rewrite(output);
readln(n,m); if n=2 then writeln(2)
else writeln(cf(2,m div 2)); close(input); close(output);
end.

原题[不是本题]的题解（1）：

Program vans;//搜索
const dx:array[1..4] of integer=(-1,0,1,0);
dy:array[1..4] of integer=(0,-1,0,1);
type arr=array[1..1000,1..1000] of boolean;
procedure search( var a:arr; var n,m:integer; x,y,sum:integer; var all:integer; var ans:int64 );
var i,u,v:integer;
begin
if sum=all then
begin
if (x=1)and(y=2) or (x=2)and(y=1) then
ans:=ans+1;
exit;
end;
for i:=1 to 4 do
begin
u:=x+dx[i]; v:=y+dy[i];
if (0<u)and(u<=n)and(0<v)and(v<=m)and(a[u,v]=false) then
begin
a[u,v]:=true;
search(a,n,m,u,v,sum+1,all,ans);
a[u,v]:=false;
end;
end;
end;
var n,m,all,sum:integer;
ans:int64;
a:arr;
begin
assign(input,'vans.in'); reset(input);
assign(output,'vans.out'); rewrite(output);
readln(n,m);
all:=n*m; sum:=1; a[1,1]:=true;
search(a,n,m,1,1,1,all,ans);
writeln(ans);
close(input); close(output);
end.

递推+高精度

递推式：

f[1]:=0; f[2]:=2; f[3]:=4; f[4]:=12; (n=5)

还有个就是： 诡异算法 by Maigo

详细见nocow http://www.nocow.cn/index.php/USACO/vans

将路径所围成的图形涂黑

把状态表示成一列中方格的颜色(状态共6种,1表示黑色,0表示白色)(竖着看!)

1 1 1 1 0 0

1 0 0 0 0 1

1 1 1 0 1 0

其中第二种的两个方格在之前没有连通，第三种是连通的

其余三种状态是不会出现的

0 1 0

1 1 0

1 0 0

方程大家可以自己想,而且我们只需要保存两列状态

（楼上的楼上，我自己推的！）

可能没化简，但是便于理解。数组的1.2.3.4.5都有很明显的意义。

这里不会贴图，讲不清，到我空间上看吧。

http://dfs35123.spaces.live.com/blog/cns!A6CB032EC0980F16!483.entry

f[2,1]:=1;

f[2,2]:=1;

for i:=3 to n do

begin

f:=f+f+f+f;

f:=f+f+f;

f:=f+f;

f:=f;

f:=f+f;

end;

writeln(2*(f[n,1]+f[n,3]));

用高精度！！

很强大的推导……总算看懂了公式是怎么推导出来的了8个情况的分析……按照列来分层只有7 和 8两种情况能出现在最后的那一层

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

f[1]=0;f[2]:=2;f[3]:=4;f[4]:=12;(N=1,2,3,4)

f[n]:=f[n-4]-f[n-3]*2+f[n-2]*2+f[n-1]*2;(N>=5)

纯粹靠高精度啦。。。公式推导还算容易，大家看下面的就行了。。。

突然发现高精度加减法用COMP压18位还不如longint压8位快。。。（>_

参考了 Maigo 诡异的算法！！

设a[i]表示第i列的左上和左下角有直线连通时的路径数，b[i]表示第i列的左上和左下角没有直线连通时的路径数，则有： b[i]:=a+b; a[i]=2+a+2(a+b+a+b+...) =2+a+2(b+b+...) 其中a[i]的值可以在计算过程中累加·！

0MS通过！

还有，加上高精度！

USACO Chapter 6.1

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        BigInteger f[] = new BigInteger[1001];
        BigInteger g[] = new BigInteger[1001];
        final BigInteger _2 = BigInteger.valueOf(2);
        f[0] = f[1] = g[0] = BigInteger.ZERO;
        f[2] = g[1] = g[2] = BigInteger.ONE;
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 3; i <= n; ++i) {
            f[i] = f[i - 1].add(g[i - 1]);
            g[i] = f[i - 1].multiply(_2).add(g[i - 1]).add(g[i - 2]).subtract(g[i - 3]);
        }
        System.out.println(f[n].multiply(_2));
    }

}

状态压缩+递推. 算是从另一个角度解释了 fammiebright的 题解吧,一个思路-_-||有比较详细的分析,题解: