某山寨

z4zr的待调教小窝

POJ2081 Recaman's Sequence DP入门

Tag:C/C++ dp poj acm

POJ2081 Recaman's Sequence DP入门

POJ2081
题目描述的是 有一个数组大小为500000
从a0 = 0 开始,m > 0
if(am > 0 并且 am没有在a数组中出现过) am = am−1 − m
else am = am−1 + m
数组示例:0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23......

开始看到题目 完全没有什么感觉。。。 就是照着描述做就行啊。。。 有木有。。 然后邪恶代码了 题目描述很清晰的啊亲。。 水水更健康

做题的时候 最开始 数组开小了。。。value和vis都开的500005 213了
am可能会很大,所以标记是否出现过的vis数组应该开大一些。。。

//14092K  16MS  787B
#include<stdio.h>
#include<string.h>
int value[500005]={0};
int i,vis[3000000]={1};
int main(){
    memset(vis+1,0,sizeof(vis));
    for(i=1;i<500001;i++){
        if((value[i-1]-i)>0&&vis[(value[i-1]-i)]==0){
            value[i]=value[i-1]-i;
        }
        else{
            value[i]=value[i-1]+i;
        }
        vis[value[i]]=1;
    }
    while(scanf("%d",&i),i!=-1){
        printf("%d/n",value[i]);
    }
    return 0;
}

内存开销好大的说。。在百度上随意的找了找解题报告。。。。
2k+的内存的木有找到。。。有3种可能:
1.更牛逼的算法。。
(或者取消vis数组,每次查询一次 用各种数据结构优化什么的。。 额 瞎想的。。 不过用最笨的方法查询肯定超时,或者用stl的set? 额 懒。。。。)
2.oj成型初期内存和时间评测不准确
3.真的懒 没有认真翻度娘。。


Warning: file_get_contents(http://api.hitokoto.us/rand): failed to open stream: Connection timed out in /data/htdocs/z4zr.host.smartgslb.com/usr/themes/Wcat/functions.php on line 87

文章二维码