一本通-1316：【例4.6】数的计数(Noip2001， 动态规划)

【题目描述】     我们要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一个自然数n（n≤1000），然后对此自然数按照如下方法进行处理：

不作任何处理； 在它的左边加上一个自然数，但该自然数不能超过原数的一半； 加上数后，继续按此规则进行处理，直到不能再加自然数为止。 【输入】 自然数n（n≤1000）。

【输出】 满足条件的数。

【输入样例】 6

【输出样例】 6

提示：满足条件的数为 6、16、26、126、36、136

---

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

vector<int> d(1005);

int solve(int n)
{
    for (int i = 3; i <= n; ++i) {
        if (!(i & 1)) d[i] = d[i - 1] + d[i >> 1];
        else d[i] = d[i - 1];
    }

    return d[n];
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;  
    cin >> n;
    d[1] = 1;
    d[2] = 2;
    cout << solve(n) << endl;

    return 0;
}

用d[i]代表i能够组成的数，如果i是奇数，那么i / 2 == (i - 1) / 2，但是如果i是偶数，则i / 2 = (i - 1) / 2 + 1。