本文共 1167 字，大约阅读时间需要 3 分钟。
| Time Limit:3000MS | | Memory Limit:60000K |
| Total Submissions:19016 | | Accepted:7963 |
Description
The Recaman's sequence is defined by a0 = 0 ; for m > 0, a
m= a
m−1− m if the rsulting a
mis 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
kto the output.
Sample Input
710000-1
Sample Output
2018658
DP水题
#include #include using namespace std;const int MAXN = 9999999;int a[MAXN];bool flag[MAXN];void DP(){ for(int i=1;i<=500000;i++) { if(a[i-1] - i > 0 && flag[a[i-1] - i] == false) { a[i] = a[i-1] - i; flag[a[i-1] - i] = true; } else { a[i] = a[i-1] + i; flag[a[i-1] + i] = true; } }}int main(){ memset(flag,false,sizeof(false)); a[0] = 0; DP(); int k; while(cin>>k) { if(k == -1) break; cout< <
转载地址：http://etyhj.baihongyu.com/