首页 > 代码库 > poj2081

poj2081

 1 //Accepted    11880 KB    0 ms 2 //dp 模拟 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 const int imax_n = 500005; 8 const int imax_flag = 10000000; 9 int a[imax_n];10 bool flag[imax_flag];11 void Dp()12 {13     memset(flag,0,sizeof(flag));14     a[0]=0;15     flag[0]=1;16     for (int i=1;i<imax_n;i++)17     {18         int temp=a[i-1]-i;19         if (temp>0 && flag[temp]==0)20         a[i]=temp;21         else22         a[i]=a[i-1]+i;23         flag[a[i]]=1;24     }25 }26 int main()27 {28     int n;29     Dp();30     while (scanf("%d",&n),n+1)31     {32         printf("%d\n",a[n]);33     }34     return 0;35 }
View Code