关键字：基础dp。
Link&Limit
时间限制：1000ms 空间限制：131072kb
Description
我们要求找出具有下列性质数的个数(包含输入的自然数n)。
先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理：
1.不作任何处理；
2.在它的左边加上一个自然数,但该自然数不能超过原数的一半；
3.加上数后,继续按此规则进行处理,直到不能再加自然数为止。
Input Format
一个自然数n 。
Output Format
满足条件的数的个数。
Sample Input #1
6
Sample Output #1
6
Hint
满足条件的数为：6，16，26，126，36，136。
对于100%的数据，n ≤ 1000.
dp基础题。令f(i)表示n为i时的答案，显然f(i) = f(1)+f(2)+...+f(i/2)+1。
#include <stdio.h>
int n,f[1010];
int main()
{
int i,j;
f[0] = 1; f[1] = 1; f[2] = 2;
scanf("%d",&n);
for(i=3;i<=n;i++)
{
for(j=(i>>1);j;j--) f[i] += f[j];
f[i]++;
}
printf("%d",f[n]);
return 0;
}
评论 (0)
