hdu 1250

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1250

思路：一开始用的是vet来保存的，速度太慢。。然后用二维数组来保存，每8位保存在数组中，处理一下进位就可以了。。。

View Code

 1 #include<iostream>
 2 using namespace std;
 3 int num[10010][300];//num[i][j]存8位
 4 
 5 
 6 void Initiate(){
 7     num[1][1]=1;
 8     num[2][1]=1;
 9     num[3][1]=1;
10     num[4][1]=1;
11     for(int i=5;i<=10000;i++){
12         for(int j=1;j<300;j++){
13             num[i][j]+=num[i-1][j]+num[i-2][j]+num[i-3][j]+num[i-4][j];
14         }
15         for(int j=1;j<300;j++){
16             //进位
17             if(num[i][j]>=100000000){
18                 num[i][j+1]+=num[i][j]/100000000;
19                 num[i][j]%=100000000;
20             }
21         }
22     }
23 }
24 
25 
26 int main(){
27     Initiate();
28     int i,n;
29     while(~scanf("%d",&n)){
30         //前导0
31         for(i=299;i>=0;i--){
32             if(num[n][i]!=0)break;
33         }
34         printf("%d",num[n][i]);
35         for(int j=i-1;j>=1;j--){
36             printf("%08d",num[n][j]);
37         }
38         printf("\n");
39     }
40     return 0;
41 }