ZOJ - 2421 Recaman's Sequence(打表水题)

题目大意：A0 = 0
Am = A(m-1) - m，如果Am小于0或者Am前面已经出现过了，那么Am ＝ A(m-1) + m

解题思路：打表水题
我用的是map，纪录数是否出现过了

#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int N = 500010;
typedef long long LL;
map<LL,int> Map;
LL num[N];

void init() {
    num[0] = 0;
    Map[0] = 1;
    LL t;
    for (int i = 1; i < N; i++) {
        t = num[i - 1] - i;
        if (t >= 0 && !Map[t]) {
            Map[t] = 1;
            num[i] = t;
        }   
        else {
            t = num[i - 1] + i;
            Map[t]=  1;
            num[i] = t;
        }
    }
}

int main() {
    init();
    int n;
    while(scanf("%d", &n) && (~n)) printf("%lld\n", num[n]);
    return 0;
}