【题目来源】
洛谷：P1028 [NOIP 2001 普及组] 数的计算 - 洛谷 (luogu.com.cn)
【题目描述】
给出正整数 \(n\)，要求按如下方式构造数列：
- 只有一个数字 \(n\) 的数列是一个合法的数列。
- 在一个合法的数列的末尾加入一个正整数，但是这个正整数不能超过该数列最后一项的一半，可以得到一个新的合法数列。
请你求出，一共有多少个合法的数列。两个合法数列 \(a,b\) 不同当且仅当两数列长度不同或存在一个正整数 \(i\le |a|\)，使得 \(a_i\neq b_i\)。
【输入】
输入只有一行一个整数，表示 \(n\)。
【输出】
输出一行一个整数，表示合法的数列个数。
【输入样例】
6
【输出样例】
6
【解题思路】
【算法标签】
《洛谷 P1028 数的计算》 #递推# #递归# #NOIP普及组# #2001#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int main() {int n;int a[1005] = {0, 1, 2}; // 初始化前三个值cin >> n; // 读取输入n// 动态规划计算序列值for (int i = 3; i <= n; i++) {if (i % 2 == 1) {// 奇数项：与前一项相同a[i] = a[i-1];} else {// 偶数项：前一项加上中间项a[i] = a[i-1] + a[i/2];}}cout << a[n]; // 输出结果return 0;
}
【运行结果】
6
6