題目大意:給出一個2*n的條形區域,問用2*1和2*2的方格一共有多少種擺放的方法。
思路:f[i] = f[i - 1] + f[i - 2] * 2
寫一個高精度加法就可以了。
CODE:
#include#include #include #include #include #define MAX 260 #define BASE 1000 using namespace std; struct BigInt{ int num[MAX],len; BigInt(int _ = 0) { memset(num,0,sizeof(num)); if(_) { num[1] = _; len = 1; } else len = 0; } BigInt operator +(const BigInt &a)const { BigInt re; re.len = max(len,a.len); int temp = 0; for(int i = 1; i <= re.len; ++i) { re.num[i] = num[i] + a.num[i] + temp; temp = re.num[i] / BASE; re.num[i] %= BASE; } if(temp) re.num[++re.len] = temp; return re; } }f[MAX]; ostream &operator <<(ostream &os,const BigInt &a) { os << a.num[a.len]; for(int i = a.len - 1; i; --i) os << fixed << setfill('0') << setw(3) << a.num[i]; return os; } int main() { f[0] = BigInt(1); f[1] = BigInt(1); f[2] = BigInt(3); for(int i = 3; i <= 250; ++i) f[i] = f[i - 1] + f[i - 2] + f[i - 2]; int x; while(scanf("%d",&x) != EOF) cout << f[x] << endl; return 0; }