HDU2044一只小蜜蜂

经典线性DP Fabonacci

1 #include
2 #include
3 #include
4 #include
5 #include
6
7 using namespace std;
8
9 inline void read(long long &x)
10 {
11 int k = 1; x = 0;
12 char c = getchar();
13 while (!isdigit(c))
14 if (c == '-') k = - 1, c = getchar();
15 else c = getchar();
16 while (isdigit(c))
17 x = (x <<1) + (x <<3) + (c ^ 48),
18 c = getchar();
19 x *= k;
20 }
21
22 long long T, a, b, dp[55], fir, las;
23
24 int main()
25 {
26 read(T);
27 for (int plk = 1; plk <= T; ++plk)
28 {
29 read(a), read(b);
30 memset(dp, 0, sizeof(dp));
31 dp[0] = 0, dp[a] = 1;
32 for (int i = a + 1; i <= b; ++i)
33 dp[i] = dp[i - 1] + dp[i - 2];
34 printf("%lld\n", dp[b]);
35 }
36 return 0;
37 }