【题目链接】

OpenJudge NOI 2.2 9273:PKU2506Tiling
OpenJudge NOI 2.3 9273:PKU2506Tiling

【题目考点】

1. 递推

2. 高精度

【解题思路】

解法1：递推

• 递推状态：aia_iai​：i列道路铺砖的方案数
• 初始状态：0列道路铺砖有1种方案，就是不铺。1列道路铺砖只有1种方案：a0=1,a1=1a_0=1, a_1=1a0​=1,a1​=1
• 递推关系：
  • 如果第i列道路只铺一个宽为1高为2的竖向的砖，那么i列道路的铺砖方案数等于前i-1列道路的铺砖方案数ai−1a_{i-1}ai−1​。
  • 如果第i列和第i-1列道路铺了两个宽为2高为1的横向的砖，那么i列道路的铺砖方案数等于前i-2列道路的铺砖方案数ai−2a_{i-2}ai−2​。
  • 如果第i列和第i-1列道路铺了一个宽为2高为2的横向的砖，那么i列道路的铺砖方案数等于前i-2列道路的铺砖方案数ai−2a_{i-2}ai−2​。
  • 以上所有情况加和，递推关系为：ai=ai−1+2∗ai−2a_i=a_{i-1}+2*a_{i-2}ai​=ai−1​+2∗ai−2​

解法2：递归

• 递归问题：求i列道路铺砖的方案数
• 递归关系：i列道路铺砖的方案数，是i-1列道路铺砖方案数加上2倍的i-2列道路铺砖的方案数（参考上面递推关系的分析方法）
• 递归出口：0列道路铺砖有1种方案，就是不铺。1列道路铺砖只有1种方案

【注意】：
因为ai=ai−1+2ai−2>2ai−2a_i=a_{i-1}+2a_{i-2}>2a_{i-2}ai​=ai−1​+2ai−2​>2ai−2​，
因此：a201>2a199>22a197>...>2100a1=2100a_{201}>2a_{199}>2^2a_{197}>...>2^{100}a_1=2^{100}a201​>2a199​>22a197​>...>2100a1​=2100，是一个高精度数字。
n最大为250，因此该题结果最大值a250a_{250}a250​也一定是一个高精度数字。
因此该题必须使用高精度计算。
估算结果的位数：
ai=ai−1+2ai−2<3ai−1<32ai−2<...<3i−1a1=3i−1a_i=a_{i-1}+2a_{i-2}<3a_{i-1}<3^2a_{i-2}<...<3^{i-1}a_1=3^{i-1}ai​=ai−1​+2ai−2​<3ai−1​<32ai−2​<...<3i−1a1​=3i−1
所以a250<3249<3250a_{250}<3^{249}<3^{250}a250​<3249<3250
求32503^{250}3250的位数⌊log103250⌋+1<250∗log103+1<250∗log1010+1=251\lfloor log_{10}3^{250}\rfloor +1<250*log_{10}3+1<250*log_{10}10+1=251⌊log10​3250⌋+1<250∗log10​3+1<250∗log10​10+1=251
因此可以把高精度数字的位数设为255。

【题解代码】

解法1：递推

• 写法1：使用全局变量和函数

#include 
using namespace std;
#define N 255 //经过估算结果位数不超过251 
void showNum(int a[])
{for(int i = a[0]; i >= 1; --i)cout << a[i];cout << endl;
}
void setLen(int a[], int i)
{while(a[i] == 0 && i > 1)i--;a[0] = i;
}
void Add(int a[], int b[]) // a += b
{int c = 0, i;for(i = 1; i <= a[0] || i <= b[0]; ++i){a[i] += b[i]+c;c = a[i]/10;a[i] %= 10;}a[i] = c;setLen(a, i);
}
int main()
{int n, a[255][N] = {};//a[i]：i列道路铺砖的方案数a[0][0] = 1, a[0][1] = 1;//a[0] = 1a[1][0] = 1, a[1][1] = 1;//a[1] = 1for(int i = 2; i <= 250; ++i)	{//a[i] = a[i-1]+2*a[i-2]Add(a[i], a[i-1]);Add(a[i], a[i-2]);Add(a[i], a[i-2]);}while(cin >> n)showNum(a[n]);return 0;
}

• 写法2：使用类和重载运算符

#include
using namespace std;
#define N 255
class HPN
{
private:int a[N];
public:HPN(){memset(a, 0, sizeof(a));}HPN(int n)//前提：n小于10{memset(a, 0, sizeof(a));a[0] = 1;a[1] = n;}int& operator [] (int i){return a[i];}HPN operator + (HPN b){HPN r;int c = 0, i;for(i = 1; i <= a[0] || i <= b[0]; ++i){r[i] = a[i] + b[i] + c;c = r[i] / 10;r[i] %= 10;}r[i] = c;while(r[i] == 0)i--;r[0] = i;return r;}void show(){for(int i = a[0]; i >= 1; --i)cout << a[i];cout << endl;}
};
int main()
{HPN a[255];//a[i]：i列道路铺砖的方案数 a[0] = HPN(1);a[1] = HPN(1);for(int i = 2; i <= 250; ++i)a[i] = a[i-1]+a[i-2]+a[i-2];//由于只重载了+运算符，因此用加法来写递推关系 int n;while(cin >> n)a[n].show();return 0;
}

解法2：递归

使用类和重载运算符，记忆化递归

#include
using namespace std;
#define N 255
class HPN
{
private:int a[N];
public:HPN(){memset(a, 0, sizeof(a));}HPN(int n)//前提：n小于10{memset(a, 0, sizeof(a));a[0] = 1;a[1] = n;}int& operator [] (int i){return a[i];}HPN operator + (HPN b){HPN r;int c = 0, i;for(i = 1; i <= a[0] || i <= b[0]; ++i){r[i] = a[i] + b[i] + c;c = r[i] / 10;r[i] %= 10;}r[i] = c;while(r[i] == 0)i--;r[0] = i;return r;}void show(){for(int i = a[0]; i >= 1; --i)cout << a[i];cout << endl;}
};
HPN a[255];//a[i]：i列道路铺砖的方案数    
HPN solve(int i)//求i列道路铺砖的方案数
{if(i == 0 || i == 1)return HPN(1); if(a[i][0])//通过看a[i]数字是否设置位数，来判断a[i]是否已经求出return a[i];elsereturn a[i] = solve(i-1) + solve(i-2) + solve(i-2);
}
int main()
{int n;while(cin >> n)solve(n).show();return 0;
}