HDU

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 int a[1005][1001] = {0}; //  假设每个都是1000位的大数 下标1表个位，2表十位...
 9 
10 //F(n) = F(n - 2) + 2 ^ (n - 3);
11 void deal()  //  提前打表
12 {
13     a[0][1] = 1;     //    表示2^(n-3)
14     a[1][1] = 0, a[2][1] = 1, a[3][1] = 1; //  第 1，2，3步的答案
15     for (int i = 4; i <= 1000; i++)    //   计算第4-1000步的答案
16     {
17         int r = 0;
18         for (int j = 1; j <= 1000; j++)  //   计算2^（n-3）
19         {
20             a[0][j] *= 2;
21             a[0][j] += r;
22             r = 0;
23             if (a[0][j] > 9)
24             {
25                 r = 1;
26                 a[0][j] -= 10;
27             }
28         }
29         r = 0;
30         for (int j = 1; j <= 1000; j++) // 计算F(n) = F(n - 2) + 2 ^ (n - 3);
31         {
32             a[i][j] = a[i - 2][j] + a[0][j] + r;;
33             r = 0;
34             if (a[i][j] > 9)
35             {
36                 r = 1;
37                 a[i][j] -= 10;
38             }
39         }
40     }
41 }
42 int main()
43 {
44     deal();
45     int n;
46     while (cin >> n)
47     {
48         if (n == 1)
49         {
50             cout << 0 << endl;
51             continue;
52         }
53         int i = 1000;
54         while (a[n][i] == 0)i--;
55         for (; i >= 1; i--)
56             printf("%d", a[n][i] );
57         printf("
");
58     }
59 }
View Code