P1028 [NOIP2001 普及组] 数的计算————C++
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
题目
[NOIP2001 普及组] 数的计算
题目描述
给出自然数 n n n要求按如下方式构造数列
- 只有一个数字 n n n 的数列是一个合法的数列。
- 在一个合法的数列的末尾加入一个自然数但是这个自然数不能超过该数列最后一项的一半可以得到一个新的合法数列。
请你求出一共有多少个合法的数列。两个合法数列 a , b a, b a,b 不同当且仅当两数列长度不同或存在一个正整数 i ≤ ∣ a ∣ i \leq |a| i≤∣a∣使得 a i ≠ b i a_i \neq b_i ai=bi。
输入格式
输入只有一行一个整数表示 n n n。
输出格式
输出一行一个整数表示合法的数列个数。
样例 #1
样例输入 #1
6
样例输出 #1
6
提示
样例 1 解释
满足条件的数列为
- 6 6 6
- 6 , 1 6, 1 6,1
- 6 , 2 6, 2 6,2
- 6 , 3 6, 3 6,3
- 6 , 2 , 1 6, 2, 1 6,2,1
- 6 , 3 , 1 6, 3, 1 6,3,1
数据规模与约定
对于全部的测试点保证 1 ≤ n ≤ 1 0 3 1 \leq n \leq 10^3 1≤n≤103。
说明
本题数据来源是 NOIP 2001 普及组第一题但是原题的题面描述和数据不符故对题面进行了修改使之符合数据。原题面如下谨供参考
我们要求找出具有下列性质数的个数包含输入的正整数 n n n。
先输入一个正整数 n n n n ≤ 1000 n \le 1000 n≤1000然后对此正整数按照如下方法进行处理
- 不作任何处理
- 在它的左边拼接一个正整数但该正整数不能超过原数或者是上一个被拼接的数的一半
- 加上数后继续按此规则进行处理直到不能再加正整数为止。
解题思路
- 递推公式。
- 设定一个数组f[n]表示数字n的答案。
函数 | 答案 |
---|---|
f[1] | 1 |
f[2] | 2 |
f[3] | 2 |
f[4] | 4 |
f[5] | 4 |
f[6] | 6 |
f[7] | 6 |
f[8] | 10 |
f[9] | 10 |
f[10] | 14 |
- 所以我们可以得出规律当n为奇数时
f[n] = f[n - 1]
;当n为偶数时f[n] = f[n - 1] + f[n / 2]
Code
#include <iostream>
using namespace std;
int main() {
int f[10005];
int t;
int ans = 0;
cin >> t; // 输入数据
f[1] = 1;
f[2] = 2;
for (int i = 3; i <= t; i++) {
f[i] = (i % 2 == 1) ? f[i - 1] : f[i - 1] + f[i / 2];
}
cout << f[t] << endl;
return 0;
}