递归--练习11--noi9273 PKU2506Tiling
一、心得
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){
二、题目
9273:PKU2506Tiling
总时间限制:
2000ms 单个测试点时间限制:
1000ms 内存限制:
131072kB
描述
对于一个2行N列的走道。现在用1*2,2*2的砖去铺满。问有多少种不同的方式。
下图是一个2行17列的走道的某种铺法。
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLi0zaHRGcWdUYuVzVa9GczoVdG1mWfVGc5RHLwkzX39GZhh2csATMflHLwEzX4xSZz91ZsADMx8FdsYkRGZkRG9lcvx2bjxSa2EWNhJTW1AlUxEFeVRUUfRHelRHL2EzXlpXazxyayFWbyVGdhd3LcV2Zh1Wa9M3clN2byBXLzN3btg3PnVGcq5iYjFDOllDZzUzM1UjN2YDOihTN0QTZ3ETZkJGMzkDM58CX0AzLchDMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjL2M3Lc9CX6MHc0RHaiojIsJye.jpeg)
输入
整个测试有多组数据,请做到文件底结束。每行给出一个数字N,0 <= n <= 250
输出
如题
样例输入
2
8
12
100
200
样例输出
3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251
三、AC代码
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 }