数的计数

Time Limit: 1 Sec  Memory Limit: 64 MB

Submit: 708  Solved: 333

Description

要求找出具有下列性质数的个数（包括输入的自然数n): 先输入一个自然数n( n <= 1000),然后对此自然数按照如下方法进行处理：（1）不作任何处理（2）在它的左边加上一个自然数，但该数不能超过原数的一半（3）加上数后，继续按此处理，直到不能再加自然数为止

Input

多个测试案例，每个测试案例输入一个自然数n

Output

输出满足以上条件的所有数的个数

Sample Input

6

Sample Output

6

HINT

对于6，满足条件的数有

6

16

26

126

36

136

1 #include
       
         2 int main() 3 { 4     int n; 5     int i,j,k; 6     int dp[1001]; 7     while(scanf("%d",&n)!=EOF) 8     { 9         for(i=0;i<=n;i++)10             dp[i]=0;11         dp[1]=1;12         for(i=2;i<=n;i++)13         {14             dp[i]=2;15             for(j=2;j<=i/2;j++)16             {17                 dp[i]+=dp[j];18             }19         }20         printf("%d\n",dp[n]);21     }22     return 0;23 }24 25         26