POJ_2229: Sumsets

2229 -- Sumsets

蟻本の動的計画法の練習問題として解いた。

考えてもわからなかったので、以下のサイトを参考にさせてもらった。最後の手段にしようと思う。

hfuji.hatenablog.jp

「漸化式を作る」という作業がまだ馴染んでない。Sample Inputだったり自分で具体例を確かめてみたり、まずは例を探って、規則性を見つけそれを式に落とし込む、という作業ができるようにしたい。

あと三項演算子の書き方を忘れていた。条件分岐が簡単に書けるので覚えておきたい。

三項演算子 (条件) ? (条件が真のとき) : (条件が偽のとき);

#include <cstdio>
#include <vector>

using namespace std;

const int M=1000000000;

int main(){
  int N;

  scanf("%d",&N);

  vector<long long int> dp(N+1);
  dp[1]=1;

  for(int i=2;i<=N;i++){
    dp[i]=(((i%2)==0) ? dp[i-1]+dp[i/2] : dp[i-1])%M;
  }

  printf("%lld\n",dp[N]);

  return 0;
}