POJ2229 Sumsets（動态規劃）

題目：SumsetsPOJ - 2229

Farmer John 讓奶牛們找一些數加起來等于一個給出的數N。但是奶牛們隻會用2的整數幂。下面是湊出7的方式

1) 1+1+1+1+1+1+1

2) 1+1+1+1+1+2

3) 1+1+1+2+2

4) 1+1+1+4

5) 1+2+2+2

6) 1+2+4

幫助FJ找到 N的配置設定數 (1 <= N <= 1,000,000).由于這個數可能很大，隻需要保留最後9位

分析：找到動歸遞推式子：

dp[i]=dp[i-1](i是奇數);dp[i]=dp[i/2]+dp[i-2](i是偶數，dp[i/2]是不含1的情況，dp[i-2]是含1的情況，由于是偶數，一旦有1，就必然有兩個1，是以減2)，注意結果是後九位，雖然覺得應該把首位的0也輸出，但是隻是模一下送出就AC了，沒辦法。。。而且，可以打表看一下dp的值，會發現10000多左右的話，long long 估計也要溢出了，是以中間結果必須模一下，至于到底模多少，反正long long範圍大，模的大一點無所謂。。。

代碼：

#include<iostream>
using namespace std;
typedef long long ll;
ll dp[1000010];
int main(){
	int n;
	cin>>n;
	dp[0]=1;
	for(int i=1;i<=n;i++){
		if(i%2==0){
			dp[i]=dp[i/2]%10000000000+dp[i-2]%10000000000;
		}
		else{
			dp[i]=dp[i-1]%10000000000;
		}
	}
	ll num=dp[n];
	/*for(int i=100000000;i>=1;i/=10){
		cout<<(num/i)%10;
	}*/
	cout<<num%1000000000;
	return 0;
}