poj 2081 Recaman's Sequence (dp)
2024-09-03 05:25:45
Recaman's Sequence
Time Limit: 3000MS | Memory Limit: 60000K | |
Total Submissions: 22566 | Accepted: 9697 |
Description
The Recaman's sequence is defined by a0 = 0 ; for m > 0, am = am−1 − m if the rsulting am is positive and not already in the sequence, otherwise am = am−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 ak.
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 ak.
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.
The last line contains an integer −1, which should not be processed.
Output
For each k given in the input, print one line containing ak to the output.
Sample Input
7
10000
-1
Sample Output
20
18658
Java AC 代码
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in);
int n = 0;
int[] result;
boolean[] marked = new boolean[10000000];
while((n = sc.nextInt()) != -1) {
result = new int[n + 1];
for(int i = 1; i < n + 1; i++) {
int a = result[i - 1] - i;
if(a > 0 && !marked[a]) {
result[i] = a;
marked[a] = true;
}
else {
result[i] = a + 2 * i;
marked[a + 2 * i] = true;
}
}
System.out.println(result[n]);
for(int i = 0; i < 10000000; i++ )
marked[i] = false;
}
}
}
最新文章
- LINQ系列:LINQ to SQL Where条件
- 利用lambda和Collection.forEach
- 在WebApi中实现Cors访问
- 笔记9:winfrom的一些知识点(二)
- 一步一步理解Paxos算法
- 【练习】创建私有的dblink
- OSGI框架学习
- maven项目在tomcat中运行遇到的问题
- 我的VSTO之路(二):VSTO程序基本知识
- jQuery选择器(ID选择器)第一节
- Android开发之漫漫长途 Ⅰ——Android系统的创世之初以及Activity的生命周期
- vs2015 c# winfrom应用程序打包成64位
- mysql 案例 ~ 函数汇总
- java学习--equals
- 使用kolla安装的openstack mariadb为集群所有节点无法启动
- mac上使用zsh配置环境变量
- PHP查找中文字符的解决方案
- 使用jar命令打jar/war包、创建可执行jar包、运行jar包、及批处理脚本编写
- css常用标签及属性
- fullpage.js全屏滚动插件使用方法