平鋪方案
ybtoj DP-1-5
題目大意
求用 1 × 2 1\times 2 1×2和 2 × 2 2\times 2 2×2的瓦片平鋪 2 × n 2\times n 2×n矩形的方案數
輸入樣例
2
8
12
100
200
輸出樣例
3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251
資料范圍
0 ? n ? 250 0\leqslant n\leqslant 250 0?n?250
解題思路
對于
2
×
2
2\times 2
2×2的瓦片只能直接放
而對于
1
×
2
1\times 2
1×2的瓦片有兩種鋪法：
1.橫著放
2.豎著放兩個，變成
2
×
2
2\times 2
2×2的瓦片
f
i
=
f
i
?
1
+
2
×
f
i
?
2
f_i=f_{i-1}+2\times f_{i-2}
fi?=fi?1?+2×fi?2?
然后高精一下即可
代碼
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n, g, f[260][110];
int main()
{
f[0][1] = 1;
f[1][1] = 1;
for (int i = 2; i <= 250; ++i)//預處理
{
for (int j = 1; j <= 100; ++j)
{
f[i][j] += f[i - 1][j] + f[i - 2][j] * 2;
f[i][j + 1] = f[i][j] / 10;
f[i][j] %= 10;
}
}
while(~scanf("%d", &n))
{
g = 100;
while(!f[n][g]) g--;
for (int i = g; i > 0; --i)
putchar(f[n][i] + 48);
putchar(10);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/240906.html
標籤：其他