首页 > 其他 > 详细

DP——数的计数

时间:2015-03-29 20:54:29      阅读:213      评论:0      收藏:0      [点我收藏+]

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

大意:还不是很清楚orz
技术分享
#include<cstdio>
#include<cstring>
using namespace std;

int main()
{
    int n;
    int dp[1100];
    scanf("%d",&n);
    dp[1] = 1;
    for(int i = 2; i <= n ;i++){
        dp[i] = 2;
       for(int j = 2; j <= i/2; j++){
            dp[i] += dp[j];
       }
    }
    printf("%d\n",dp[n]);
   return 0;
}
View Code

 

DP——数的计数

原文:http://www.cnblogs.com/zero-begin/p/4376223.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!