POJ 2506 高精度+递推

9月 14

题目大意就是有 $2 \times 1$ 和 $2 \times 2$ 两种规格的地板，现要拼 $2 \times n$ 的形状，共有多少种情况，首先要做这道题目要先对递推有一定的了解。
假设我们已经铺好了 $2 \times (n-1)$ 的情形，则要铺到 $2 \times n$ 则只能用 $2 \times 1$ 的地板
假设我们已经铺好了 $2 \times (n-2)$ 的情形，则要铺到 $2 \times n$ 则可以选择1个 $2 \times 2$ 或两个 $2 \times 1$ ，故可能有下列三种铺法

其中要注意到第三个会与铺好 $2 \times (n-1)$ 的情况重复，故不可取，故可以得到递推式 $a_i=2a_{i-2}+a_{i-1}$

然后就是高精度部分，可直接用高精度的模板

直接套用模板就1A了，只是简单的递推题，算是练习套模板能力或验证模板的正确性吧！

poj2506 Tilingview raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include <deque>
#include <vector>
using namespace std;

const int Base=1000000000;  
const int Capacity=100;  
typedef long long huge;    

struct BigInt{  
     int Len;  
     int Data[Capacity];  
     BigInt() : Len(0) {}  
     BigInt (const BigInt &V) : Len(V.Len) { memcpy (Data, V.Data, Len*sizeof*Data);}  
     BigInt(int V) : Len(0) {for(;V>0;V/=Base) Data[Len++]=V%Base;}  
     BigInt &operator=(const BigInt &V) {Len=V.Len; memcpy(Data, V.Data, Len*sizeof*Data); return *this;}  
     int &operator[] (int Index) {return Data[Index];}  
     int operator[] (int Index) const {return Data[Index];}  
};

BigInt operator+(const BigInt &A,const BigInt &B){  
     int i,Carry(0);  
     BigInt R;  
     for(i=0;i<A.Len||i<B.Len||Carry>0;i++){  
         if(i<A.Len) Carry+=A[i];  
         if(i<B.Len) Carry+=B[i]; 
         R[i]=Carry%Base;  
         Carry/=Base;  
     }  
     R.Len=i;  
     return R;  
}

ostream &operator<<(ostream &Out,const BigInt &V){  
     int i;  
     Out<<(V.Len==0 ? 0:V[V.Len-1]);  
     for(i=V.Len-2;i>=0;i--) for(int j=Base/10;j>0;j/=10) Out<<V[i]/j%10;  
     return Out;  
}

BigInt ans[300];

int main()
{
    ans[0]=1;
    ans[1]=1;
    int i;
    for ( i = 2  ; i <= 250 ; i ++ )
    {
        ans[i]=ans[i-2]+ans[i-1]+ans[i-2];
    }
    int n ;
    while ( cin >> n )
        cout<<ans[n]<<endl;
    return 0;
}