洛谷P1028数的计算

题面

题目大意

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

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

1、不作任何处理;

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

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

输入格式

1个自然数n(n <= 1000)

输出格式

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

思路

我们可以按照题目给的6来枚举一下
6的方案有6种
6，16，26，36，126，136
稍微推导一下
设 f [ i ] 为 i 的方案数
可得

突然感觉有点像斐波那契
又有点像dp
但就是递推

这本是一道递推题目，所以就不按其他方法做了，递推代码直接上

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int f[1001];//存每一位数的方案

int main()
{
    cin>>n;
    for(int i = 1; i <= n; i++)
    { 
        for(int j = 1; j <= i / 2; j++)
            f[i] += f[j]; //每一位叠加

        f[i]++; //加上本身（方案数+1）
    }
    cout<<f[n];//输出n的方案
    return 0;
}

因为到了算法就要开始烧脑了，我虽然是腐败党的，但也劝新手，少腐败，多做题，动动脑子，专心做题，别堕落了哦~~！