codevs1011 数的计算 2001年NOIP全国联赛普及组

题目描述 Description

我们要求找出具有下列性质数的个数(包含输入的自然数n):

先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:

1.          不作任何处理;

2.          在它的左边加上一个自然数,但该自然数不能超过原数的一半;

3.          加上数后,继续按此规则进行处理,直到不能再加自然数为止.

输入描述 Input Description

一个数n

输出描述 Output Description

满足条件的数的个数

样例输入 Sample Input

6

样例输出 Sample Output

6

数据范围及提示 Data Size & Hint

6个数分别是：

6

16

26

126

36

136

---

　　要不是说明了是递推还想不到，半夜没做出，早上在刷牙的时候想出了，很有意思的题。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cstdlib>
#include<cmath>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <stack>
#include <cctype>
using namespace std;
typedef unsigned long long ull;
#define INF 0xfffffff

//0:1;1:1;2:2;3:2;

int main()
{
    int T;
    int a[1000],b;
    while(cin>>b)
    {
        memset(a,0,sizeof(a));
        a[0]=1;a[1]=1;
        for(int i=2;i<=b;++i)
            for(int j=0;j<=i/2;++j)
                a[i]+=a[j];
        cout<<a[b]<<endl;
    }

    
    return 0;
}