dp递推poj2801

http://poj.org/problem?id=2081

要的就是存储中间数据的思想，避免重复计算

Source Code

Problem: 2081        User: 297752873
/*Memory: 41280K        Time: 32MS
Language: C        Result: Accepted
Source Code*/
#include<stdio.h>
#include<string.h>
    int a[500001],hash[10000000];
int main()
{
    int i,k;
    memset(hash,0,sizeof(hash));
    a[0]=0;hash[0]=1;
    for(i=1;i<500001;i++)
    {
       if(a[i-1]-i>0&&!hash[a[i-1]-i])
       a[i]=a[i-1]-i;
       else a[i]=a[i-1]+i;
       hash[a[i]]=1;
    }
    while(scanf("%d",&k),k!=-1)
    printf("%d
",a[k]);
    return 0;
}