POJ2081总结

Recaman’s Sequence

题目来源

Description

The Recaman’s sequence is defined by a0 = 0 ; for m > 0, a_m = a_m−1 − m if the rsulting a_m is positive and not already in the sequence, otherwise a_m = a_m−1 + m.
The first few numbers in the Recaman’s Sequence is 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9 …
Given k, your task is to calculate a_k.

Input

The input consists of several test cases. Each line of the input contains an integer k where 0 <= k <= 500000.
The last line contains an integer −1, which should not be processed.

Output

For each k given in the input, print one line containing a_k to the output.

Sample Input

7
10000
-1

Sample Output

20
18658

我的代码

这题也太老实了，直接告诉了dp方程，唯一值得处理的是任何去重，其实空间给的足够大，只要开一个数组就够了。

#include<stdio.h>

int dp[500010]={0};
int flag[5000010]={0};
int main()
{
	for (int i=1;i<500010;i++){
		if(dp[i-1]-i>0&&flag[dp[i-1]-i]==0){
			dp[i]=dp[i-1]-i;
		}else{
			dp[i]=dp[i-1]+i;
		}
		flag[dp[i]]=1;
	}
	int k;
	while(scanf("%d",&k)==1&&k!=-1){
		printf("%d\n",dp[k]);
	}
	return 0;
}