NBU 1409(模拟题）

题目链接：http://ac.nbutoj.com/Problem/view.xhtml?id=1409
思路：一道不错的题，递推关系式之后还得处理大数。
View Code
 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 const int MAXN=110;
 8 int dp1[MAXN][MAXN],dp2[MAXN][MAXN];
 9 int ans[MAXN][MAXN];
10 //dp1[i]表示走i步朝上走的方案数
11 //dp2[i]表示走i步左走或右走的方案数
12 //dp1[i]=dp1[i-1]+dp2[i-1];
13 //dp2[i]=2*dp1[i-1]+dp2[i-1];
14 //ans[i]=dp1[i]+dp2[i];
15 
16 void Solve1(int dp1[],int a[],int b[]){
17     for(int i=0;i<MAXN;i++){
18         dp1[i]+=a[i]+b[i];
19         if(dp1[i]>=10){
20             dp1[i+1]=dp1[i]/10;
21             dp1[i]%=10;
22         }
23     }
24 }
25 
26 void Solve2(int dp2[],int a[],int b[]){
27     for(int i=0;i<MAXN;i++){
28         a[i]=2*a[i];
29     }
30     for(int i=0;i<MAXN;i++){
31         dp2[i]+=a[i]+b[i];
32         if(dp2[i]>=10){
33             dp2[i+1]=dp2[i]/10;
34             dp2[i]%=10;
35         }
36     }
37 }
38 
39 
40 int main(){
41     dp1[1][0]=1;
42     dp2[1][0]=2;
43     ans[1][0]=3;
44     for(int i=2;i<MAXN;i++){
45         Solve1(dp1[i],dp1[i-1],dp2[i-1]);
46         Solve2(dp2[i],dp1[i-1],dp2[i-1]);
47         Solve1(ans[i],dp1[i],dp2[i]);
48     }
49     int n;
50     while(~scanf("%d",&n)){
51         bool flag=true;
52         for(int i=MAXN-1;i>=0;i--){
53             if(ans[n][i]==0&&flag)continue;
54             else {
55                 flag=false;
56                 printf("%d",ans[n][i]);
57             }
58         }
59         puts("");
60     }
61     return 0;
62 }