洛谷 P1028 数的计算

链接

https://www.luogu.org/problemnew/show/P1028

题目

题目描述

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

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

不作任何处理;
在它的左边加上一个自然数,但该自然数不能超过原数的一半;
加上数后,继续按此规则进行处理,直到不能再加自然数为止.

输入输出格式

输入格式：

1个自然数n(n≤1000)

输出格式：

1个整数，表示具有该性质数的个数。

输入输出样例

输入样例#1：

输出样例#1：

说明

满足条件的数为

6，16，26，126，36，136

思路

题目不难，就是有点没说清楚，也可能是我语文不好emmm。思路就是找的所以可能数的数量，寻找方法是在左侧加入一个小于自身一半的数，加上之后继续寻找，直到那个数为1无法继续添加，而且这个加的数，是上次添加的数的一半。

暴力递归一看就会超时，这种题肯定不能这么做。（如果你打算递归打表那就当我没说）

这边我就先以上限值1000，999，998作为样例。

1000的左侧可以放自身一半以下的数，就是500,499一直到1；f（1000）

999的左侧也是，不过不能放500，只能499到1；f（999）

998的左侧就是499到1，和999相同；f（998）。

综上所述，f（1000）= f（999）+f （500），f（999）= f（998），

推广可以找到规律：

当n为偶数时：f（n）= f（n-1） + f（n/2）；

当n为奇数时：f（n）= f（n-1）

所以直接初始化f（0），f（1），之后计算即可。

代码

#include<iostream>

using namespace std;

int main()
{
    int n, f[1024];
    cin>>n;
    f[0] = 1;
    f[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(i%2==0)
            f[i] = f[i/2]+f[i-1];
        else
            f[i] = f[i-1];
    }
    cout<<f[n];
    return 0;
}