题面
题目大意
我们要求找出具有下列性质数的个数(包含输入的自然数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;
}
因为到了算法就要开始烧脑了，我虽然是腐败党的，但也劝新手，少腐败，多做题，动动脑子，专心做题，别堕落了哦~~！
