线上OJ:
一本通:1914:【01NOIP普及组】数的计数 (opens in a new tab)
AcWing:5496. 数的计算 (opens in a new tab)
核心思想:
1、样例中给到了 。其实这里包含了 , 以及6本身。
注解:按照题意,6前面的数字只能是3,2,1,或者不放(不放就是6本身)
当6前面放3的时候,那3有多少种可能性,就都可以叠加在这里。即
同理,当6前面放2的时候,2的所有可能性也都叠加在这里
同理,当6前面放2的时候,2的所有可能性也都叠加在这里
最后,加上6自己本身,所以
2、综上所述,我们可以从 开始逐步计算每个 ,直到 (时间复杂度是
3、最后根据输入的 n,直接输出 即可。
题解代码:
数的计数
#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int n, f[N];
int main()
{
f[1] = 1; // 初始化 f[1],就只有自己
for (int i = 2; i <= N; i++)
{
int x = i / 2; // 针对每一个i,找到它不能超过的一半
for(int j = 1; j <= x; j++)
f[i] += f[j]; // 累加
f[i]++; // 最后加上自己
}
scanf("%d", &n);
printf("%d", f[n]);
return 0 ;
}