宣城建设网站,杭州滨江网站建设公司,政务网站安全建设工作计划,网站建设与运营 pdf题目描述
给出正整数 n#xff0c;要求按如下方式构造数列#xff1a;
只有一个数字 n 的数列是一个合法的数列。在一个合法的数列的末尾加入一个正整数#xff0c;但是这个正整数不能超过该数列最后一项的一半#xff0c;可以得到一个新的合法数列。
请你求出#xff…题目描述
给出正整数 n要求按如下方式构造数列
只有一个数字 n 的数列是一个合法的数列。在一个合法的数列的末尾加入一个正整数但是这个正整数不能超过该数列最后一项的一半可以得到一个新的合法数列。
请你求出一共有多少个合法的数列。两个合法数列 a,b不同当且仅当两数列长度不同或存在一个正整数 i≤∣a∣使得 ai≠bi
输入格式
输入只有一行一个整数表示 n。
输出格式
输出一行一个整数表示合法的数列个数。
输入输出样例
输入 #1
6输出 #1
6说明/提示
样例 1 解释
满足条件的数列为
66,16,26,36,2,16,3,1
数据规模与约定
对于全部的测试点保证 1≤n≤1000
解题分析
本题的递推其实并不困难主要是关于递归函数的一个设计。我们假定f(n)表示对于给定的正整数n它得到的序列个数。那么我们可以将其与更小的数所形成的序列个数进行关联。例如说例子中的6, 它所形成的序列首先有它自己本身吧。然后对于小于等于它的二分之一的数都可以继续接在这个序列的后面。
所以我们可以得到f(n)f(1)f(2)....f(m)其中mn/2那么本题就解决了。
#include iostream
#include cmath
#include iomanip
using namespace std;
int dp[1005];
int f(int n){if(n1){return 1;}if(dp[n]) return dp[n];int mn/2;int res1;for(int i1;im;i){resf(i);}return dp[n]res;
}int main(){int n; cinn;coutf(n)endl;return 0;
}
