又在洛谷上刷题。

又是一题，

P1028 数的计算

来，咱读题：

题目描述

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

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

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

输入格式

11个自然数nn(n \le 1000n≤1000)

输出格式

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

输入输出样例

输入 #1

1
6

输出 #1

1
2
6

说明/提示

满足条件的数为

6，16，26，126，36，136

看完题，这题不很简单吗？一个递归不就解决？

满怀信心地写程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int s=0;
int js(int a)
{
    a/=2;
    for(int i=1;i<=a;i++)
    {
        s++;
        js(i);
    }
    return s;
}
int main()
{
    int n;
    cin>>n;
    cout<<js(n)+1;
}

一下F5都没有按（我用的Visual Studio 2019），就满怀信心的提交。

结局并不是我想象的那样，而是这样：

（开始怀疑）

自己试了一下，果然：

这好歹也是个I7-6700K

怎么也不知道应该怎样改进，只好查看了一下题解，发现题解使用的是递推算法。

我们以4为例子来进行说明

4后面可以跟上1,2组成14,24

14后面跟不了,24可以跟上1组成124

再加上4本身就可以得到4的种类

即 14,24,124,4

而我们只要算出1,2的种类就可以加起来得到4的种类

因此，我们得到

1
2
3
4
5
1 f[1]=1
2 f[2]=2=f[1]+1
3 f[3]=2=f[1]+1
4 f[4]=4=f[1]+f[2]+1
5 f[5]=4=f[1]+f[2]+1

以此类推，我们得到以下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int fuc[1000];
int main()
{ 
    int n;
    cin>>n;
    for(int i=0;i<=n;i++)
    {
        for(int j=1;j<=i/2;j++)
        {
            fuc[i]+=fuc[j];
        }
        fuc[i]++;//还要加上这个数本身 
    }
    cout<<fuc[n];
    return 0;
}

我就发现了自己算法的问题：

递推算法每算好一个数，下一个数就只需要加起来就行了；而递归算法每个数都要重新计算，自然效率低。