hdu Children’s Queue

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 300000
 5 using namespace std;
 6 
 7 int n;
 8 int a[1001][500];
 9 
10 void inti()
11 {
12     a[1][0]=1;
13     a[2][0]=2;
14     a[3][0]=4;
15     a[4][0]=7;
16     for(int i=5; i<=1000; i++)
17     {
18         int c=0;
19         for(int j=0; j<=300; j++)
20         {
21             a[i][j]=a[i-1][j]+a[i-2][j]+a[i-4][j]+c;
22             c=a[i][j]/10;
23             a[i][j]%=10;
24         }
25     }
26 }
27 
28 int main()
29 {
30     inti();
31     while(scanf("%d",&n)!=EOF)
32     {
33         int i=4a99;
34         while(i>=0&&!a[n][i]) i--;
35         while(i>=0)
36         {
37             printf("%d",a[n][i]);
38             i--;
39         }
40         printf("
");
41     }
42     return 0;
43 }