DP 之 poj 2229

//  [3/24/2014 Sjm]
/*
解法分析：
依次列出 N=1, 2, 3, 4, 5, 6, 7, 寻找规律：
(1) 若 n 为奇数：dp[n] = dp[n - 1] （第一个数必是1， 将第一个数去掉， 其所剩个数 即 dp[n-1]）
(2) 若 n 为偶数：
	1) 第一个数字为1，将第一个数去掉， 其所剩个数 即 dp[n-1]
	2）第一个数为偶数(所有的这一排数均为偶数)， 将2提出去，即可得 dp[n>>1]
	两者加和，即为答案。
*/

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 #include <vector>
 5 using namespace std;
 6 const int Mod = 1e9;
 7 int N;
 8 
 9 int Solve()
10 {
11     vector<int> dp(N+1);
12     dp[1] = 1; 
13     for (int i = 2; i <= N; i++){
14         if (i & 1) dp[i] = dp[i - 1];
15         else dp[i] = (dp[i - 1] + dp[i >> 1]) % Mod;
16     }
17     return dp[N];
18 }
19 
20 int main()
21 {
22     //freopen("input.txt", "r", stdin);
23     //freopen("output.txt", "w", stdout);
24     while (scanf("%d", &N) != EOF)
25         printf("%d\n", Solve());
26     return 0;
27 }