Initiate

给看似复杂的题找到了合适的规律就会变得简单。

这个题就是这样。对于n列来说，可以在n-1列的基础上加上一块，或者是在n-2列的基础上加上2块

而2块独立的，不依赖于1块的情况有两种，所以得到递推公式f(n)=f(n-1)+2f(n-2)

看样例，要用到高精。

#include<iostream>
//f(n)=f(n-1)+2f(n-2)
using namespace std;
int f[251][300];
void HPprint(int *a)
{
    for (int i=a[0];i>=1;i--) cout<<a[i];
    cout<<endl;
}

void HPplus(int *a,int *b,int *c)
{
int i,j;
j=0;
for(i=1;i<=min(a[0],b[0]);i++)
{
   c[i]=a[i]+b[i]+j;
   j=c[i]/10;
   c[i]%=10;
   }
if(j!=0) c[i]=j;
c[0]=a[0]>b[0]?a[0]+2:b[0]+2;
while(c[c[0]]==0 && c[0]>1) c[0]--;
}
void HPmultyNUM(int *a,int b,int *c)
{
    int i,j,k;
    for (i=1;i<=a[0];i++)
        c[i]+=a[i]*b;
        k=0;
    for (j=1;j<=a[0];j++)
        {
            c[j]+=k;
            k=c[j]/10;
            c[j]%=10;
        }//进位
    if(k!=0) c[j]=k;
    c[0]=a[0]+3;
    while (c[c[0]]==0 && c[0]>1) c[0]--;   
}
int main()
{
int i,j,t[300],test;
f[0][0]=1;f[0][1]=1;
f[1][0]=1;f[1][1]=1;f[2][0]=1;f[2][1]=3;
for(i=3;i<=250;i++)
{
   memset(t,0,sizeof(t));
   HPmultyNUM(f[i-2],2,t);
   HPplus(t,f[i-1],f[i]);
}
while(cin>>test)
   HPprint(f[test]);
return 0;
}