洛谷 P1028 [NOIP 2001 普及组] 数的计算（动态规划）

题目描述给出正整数 n要求按如下方式构造数列只有一个数 n 的数列是一个合法的数列。在一个合法的数列的末尾加入一个正整数但是这个正整数不能超过该数列最后一项的一半可以得到一个新的合法数列。请你求出一共有多少个合法的数列。两个合法数列 a,b 不同当且仅当两数列长度不同或存在一个正整数 i≤∣a∣使得 a[i]!b[i]。输入格式输入只有一行一个整数表示 n。输出格式输出一行一个整数表示合法的数列个数。输入输出样例输入6输出6说明/提示样例 1 解释满足条件的数列为66,16,26,36,2,16,3,1数据规模与约定对于全部的测试点保证 1≤n≤103我的思路动态规划第一步确定状态。确定状态可以用“最后一步法”就是根据这个问题的最后一步确定状态具体代表什么。然后把大问题转化为子问题就像这道题的大问题“求正整数n一共有多少个合法子序列”我们可以化为很多个子问题从0开始求它一共有多少个合法子序列一直到n。我把题目中的问题确定为状态也就是“一共有多少个合法的数列”。可以创建一个数组a而a[i]的意义是“第i个数所拥有的全部数列”如:a[1]1,a[2]2,a[3]2…。动态规划第二步列出状态转移方程。我们根据子问题确定状态转移方程a[i]a[0]a[1]a[2]…a[i/2]。也可以找规律0—01—12—23—24—45—56—67—68—109—10。我们把每个数所有的数列列出来如666 16 26 2 16 36 3 1。能发现6的数列由0123的最多数列组成。由此可得上面的状态转移方程。动态规划第三步确定边界。这道题的边界可以定为a[0]1或a[0]a[1]1…,根据个人习惯。但是要注意for循环中i和j的值要变化。动态规划第四步计算根据由子问题逐渐合并为大问题过程进行计算。以下是我的代码#includebits/stdc.husingnamespacestd;constintmaxn1e310;inta[maxn];intmain(){intn;cinn;a[0]a[1]1;for(inti2;in;i){for(intj0;ji/2;j){a[i]a[j];}}couta[n];return0;}题目来源洛谷P1028 [NOIP 2001 普及组] 数的计算