POJ9273:PKU2506Tiling_递推+高精度

总时间限制: 2000ms 单个测试点时间限制: 1000ms 内存限制: 131072kB

描述

对于一个2行N列的走道。现在用12,22的砖去铺满。问有多少种不同的方式。

下图是一个2行17列的走道的某种铺法。
POJ9273:PKU2506Tiling_递推+高精度

输入

整个测试有多组数据,请做到文件底结束。每行给出一个数字N,0 <= n <= 250

输出

如题

样例

样例输入

2
8
12
100
200

样例输出

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

思考

  1. 看到输出的结果,显然long long int 肯定是不够用的,所以要用到高精度加减法用数组来存储数字
  2. 可以发现完整覆盖两行的方式只有三种:两个1*2的砖覆盖两行两列、一个1*2的砖覆盖两行一列、一个2*2的砖覆盖两行两列。不如设g(n)为剩余n列时的铺满方式,那么得到递推公式:g(n) = 2*g(n-2) + g(n-1),递归的出口为g(1) = 1g(2) = 3
  3. 递推公式的实现有两种,一种是自底向上(动态规划),一种是自顶向下(递归)。如果采用递归调用,显然时间复杂度为O(3^n)直接爆掉,所以我们在此采用动态规划自底向上求解。
  4. 特别注意一个地方,n的取值范围包含0,所以要特判g(0) = 1

AC代码

#include<bits/stdc++.h>
using namespace std;
int a[300][1000];//a[i][j]表示还剩下i列时的第j位,a[i][0]存储数字的长度
int main(){
	memset(a,0,sizeof(a));
	//递推边界条件
	a[1][0] = 1,a[1][1] = 1;
	a[2][0] = 1,a[2][1] = 3;
	for(int i=3;i<=250;i++){
		//对每一位套用递推公式
		for(int j=1;j<=max(a[i-1][0],a[i-2][0]);j++){
			a[i][j] = a[i-1][j] + a[i-2][j]*2;
		}
		a[i][0] = max(a[i-1][0],a[i-2][0]);
		//注意要进位
		for(int j=1;j<=a[i][0];j++){
			if(a[i][j]>=10){
				a[i][j+1] += a[i][j]/10;
				a[i][j] = a[i][j]%10;
			}
		}
		if(a[i][a[i][0]+1]){
			a[i][0]++;
		} 	
	}
	int n;
	while(cin>>n){
		if(n==0){
			cout<<1<<'\n';
		}
		else{ 
			for(int j=a[n][0];j>=1;j--){
				cout<<a[n][j]; 
			}
			cout<<'\n';
		} 
	} 
return 0;
} 

采用高精度后,时间复杂度降低到O(n*最大位数)
参考:@zqwang博主

上一篇:java 往 pdf 插入数据 (pdfbox+poi)


下一篇:PTA习题