递归--练习11--noi9273 PKU2506Tiling

9273:PKU2506Tiling

总时间限制: 

2000ms

 

单个测试点时间限制: 

1000ms

 

内存限制: 

131072kB

描述

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

下图是一个2行17列的走道的某种铺法。

输入

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

输出

如题

样例输入

2
8
12
100
200

样例输出

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

  1 /*
  2 noi9273 PKU2506Tiling
  3 
  4 就是好好找子问题就好了
  5  
  6 找出递推关系式即可：
  7 第一块1*2横放：
  8 f(n)=f(n-2)
  9 第一块1*2竖放：
 10 f(n)=f(n-1) 
 11 第一块2*2：
 12 f(n)=f(n-2)
 13 
 14 故f(n)=f(n-1)+2*f(n-2);
 15 边界条件
 16 f(0)=1
 17 f(1)=1
 18 f(2)=3 
 19 
 20 高精度 (用个2维数组把每一个数的每一位都存下来即可)
 21 其实加和乘里面只需要有加，因为乘2完全可以看成想加 
 22 记忆化递归 
 23 
 24 
 25 a[i]%=10;
 26 这里错了，花了好久改好 
 27 
 28 
 29 int* f(int n){
 30     if(dp[n][0]!=0) return dp[n];
 31     else if(0==n) return dp[0];
 32     else if(1==n) return dp[1];
 33     else{
 34         
 35         give(jia(f(n-1),chen(f(n-2),2)),dp[n]);
 36         return dp[n];
 37     }
 38 } 
 39 直接这样写的话f(n-1)那些的值一直被改变 ,指针需要去看看
 40 二维指针就是地址 
 41 
 42 整个测试有多组数据，请做到文件底结束。
 43 while(scanf("%d",&n)!=EOF){
 44 */
 45 #include <iostream>
 46 #define Max 300
 47 using namespace std;
 48 int dp[Max][Max];//用个2维数组把每一个数的每一位都存下来
 49 //打印结果 
 50 void print(int dp[]){
 51     for(int i=dp[0];i>=1;i--){
 52         cout<<dp[i];
 53     }
 54     cout<<endl;
 55 }
 56 //高精度乘单精度 
 57 int* chen(int a[],int b){
 58     //乘 
 59     for(int i=1;i<=a[0];i++){
 60         a[i]*=b;
 61     } 
 62     //处理进位
 63     for(int i=1;i<=a[0];i++){
 64         if(a[i]>=10){
 65             a[i]%=10;
 66             a[i+1]++;
 67         }
 68     }  
 69     //更正位数
 70     while(a[a[0]+1]>0) a[0]++; 
 71     return a;
 72 } 
 73 //高精度加法 
 74 int* jia(int a[],int b[]){
 75     if(a[0]<b[0]) a[0]=b[0];
 76     //加
 77     for(int i=1;i<=a[0];i++){
 78         a[i]+=b[i];
 79     } 
 80     //处理进位
 81     for(int i=1;i<=a[0];i++){
 82         if(a[i]>=10){
 83             a[i]%=10;
 84             a[i+1]++;
 85         }
 86     } 
 87     //更正位数
 88     while(a[a[0]+1]>0) a[0]++; 
 89     return a;
 90 
 91 }
 92 //赋值，把ans数组的值全部给dp数组 
 93 void give(int ans[],int dp[]){
 94     for(int i=0;i<=ans[0];i++){
 95         dp[i]=ans[i];
 96     }
 97 } 
 98 int* f(int n){
 99     if(dp[n][0]!=0) return dp[n];
100     else if(0==n) return dp[0];
101     else if(1==n) return dp[1];
102     else{
103         int tmp_1[Max]={0};
104         int tmp_2[Max]={0};
105         give(f(n-1),tmp_1);
106         give(f(n-2),tmp_2);
107         give(jia(tmp_1,chen(tmp_2,2)),dp[n]);
108         return dp[n];
109     }
110 } 
111 
112 int main(){
113     dp[0][0]=1,dp[0][1]=1;//前面是位数，后面是数 
114     dp[1][0]=1,dp[1][1]=1;
115     int n=100;
116     while(scanf("%d",&n)!=EOF){
117         f(n);
118         print(dp[n]); 
119     }
120     return 0;
121 }