POJ 2081 Recaman's Sequence

106 阅读 0 评论 70 点赞

我是靠谱客的博主飘逸台灯，这篇文章主要介绍POJ 2081 Recaman's Sequence，现在分享给大家，希望可以做个参考。

很简单题，直接暴力运算。前人们都说这道题是简单DP，比较有道理

不过我觉得这道题好像模拟以下计算过程就完事了，不过想起来DP也是在模拟计算过程。。。结果我在网上也没查到模拟法的定义

这道题比较有意思的是数组范围，超~~~~大，本地根本无法通过，不过OJ上可以

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>
#include<string.h>
#define max 10000000
#define N 500002
int a[N];
char vis[max];
// 数组要开成全局
int main(void){
int n, m;
memset( vis, 0, sizeof(vis));
memset( a, 0, sizeof(a));
for( m = 1; m < N; m++){
if( a[m-1] - m > 0 && !vis[a[m-1] - m]){
a[m] = a[m-1] - m;
vis[a[m]] = 1;
}
else{
a[m] = a[m-1] + m;
vis[a[m]] = 1;
}
}
while( scanf("%d", &n) != EOF && n != -1){
printf("%dn", a[n]);
}
return 0;
}