P1028 [NOIP2001 普及组] 数的计算

题目描述

给出正整数 $n$，要求按如下方式构造数列：

1. 只有一个数 $n$ 的数列是一个合法的数列。
2. 在一个合法的数列的末尾加入一个正整数，但是这个正整数不能超过该数列最后一项的一半，可以得到一个新的合法数列。

请你求出，一共有多少个合法的数列。两个合法数列 $a,b$ 不同当且仅当两数列长度不同或存在一个正整数 $i\le \mid a\mid$，使得 $a_i\ne b_i$。

详见题目[P1028 NOIP2001 普及组] 数的计算 - 洛谷 | 计算机科学教育新生态

输入格式

输入只有一行一个整数，表示 $n$。

输出格式

输出一行一个整数，表示合法的数列个数。

输入输出样例

输入 #1

6

输出 #1

6

说明/提示

样例 1 解释

满足条件的数列为：

• $6$
• $6,1$
• $6,2$
• $6,3$
• $6,2,1$
• $6,3,1$

数据规模与约定

对于全部的测试点，保证$ 1≤n≤10^3$。

题解

设$f[i]$为初始值为$i$时满足条件的方案总数，因在合法序列加入的数字将不大于序列的最后一位数，易得：
$$f[n]=\sum _1^{n/2}f(i)$$
同时：

• $i=2n+1时，f[i]=f[i-1]$
• $i=2n时,f[i]=f[i-1]+f[\frac{i}{2}]$

同时初始化数组，$f[1]=1$：

#include<iostream>
using namespace std;
int n, f[10005];int main()
{cin >> n;f[1] = 1;for(int i = 2; i <= n ; i ++){f[i] = f[i - 1];if(i % 2 == 0)f[i] = f[i - 1] + f[i / 2];}cout << f[n] << endl;return 0;
}

或者这样套两个循环：

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

以此类推即可：

#include<iostream>
using namespace std;
int n, f[10005];int main()
{cin >> n;f[1] = 1;for(int i = 2; i <= n; i ++){for(int j = 1; j <= i / 2; j ++)f[i] += f[j];f[i] ++;}cout << f[n] << endl;return 0;
}