POJ 2081 Recaman's Sequence

問題文

DP強化週間。

問題概要は簡単なので略。

問題も小さい方からメモ化して計算していくだけ。
以下ソース。

int a[500001];

int main(int argc, char **argv){
  a[0] = 0;
  set<int> rec;
  for(int i = 1; i <= 500000; i++){
    int t = a[i - 1] - i;
    int u = a[i - 1] + i;
    set<int>::iterator it = rec.find(t);
    if(t > 0 && it == rec.end()){
      a[i] = t;
      rec.insert(t);
    }else{
      a[i] = u;
      rec.insert(u);
    }
  }

  int k;
  while(cin >> k, k != -1)
    cout << a[k] << endl;
  return 0;
}

DP強化週間が終わったら、数学問題を少しやるべきだと思う。