2229 Sumsets

http://poj.org/problem?id=2229

方針

nが偶数の時
f(n) = f(n/2) + f(n-2)
nが奇数の時
f(n) = f(n-1)
となるため、小さい方から順に求めてやる

ソース

#include<iostream>
#include<string.h>
using namespace std;

long long memo[1000020];

int main() {
  memset(memo, 0, sizeof(memo));
  int n;
  cin>>n;
  memo[0] = 0;
  memo[1] = 1;
  memo[2] = 2;
  for(int i=3; i<=1000000; ++i) {
    if(i%2) memo[i] = memo[i-1];
    else {
      memo[i] = (memo[i/2] + memo[i-2])%1000000000ll;
    }
  }
  cout<<memo[n]<<endl;
}