关键字：基础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。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #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)
