本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】学而思编程购买模型【题目描述】商店里有n nn个模型编号为1 ∼ n 1∼n1∼n第i ii个模型的尺寸为s i s_isi。小猴想要购买若干个模型他对购买的模型有以下要求1编号从小到大排序后对所有相邻的模型后一个的编号是前一个的倍数。2编号从小到大排序后对所有相邻的模型后一个的尺寸严格大于前一个的尺寸。我们认为只购买1 11个模型也满足要求。例如有6 66个模型大小是[ 3 , 6 , 7 , 3 , 7 , 7 ] [3,6,7,3,7,7][3,6,7,3,7,7]那么小猴可以买第1 , 2 , 6 1,2,61,2,6个模型它们的尺寸是 $[3,6,7]但是小猴不可以购买第1 , 2 , 3 1,2,31,2,3个因为编号3 33不是它前一个编号2 22的倍数小猴也不可以购买第1 , 2 , 4 1,2,41,2,4个因为这三个的尺寸[ 3 , 6 , 3 ] [3,6,3][3,6,3]不是严格升序。小猴想知道他最多可以购买多少个模型。输入包含多组数据。【输入】第1 11行1 11个正整数T TT表示有T TT组数据。接下来2 T 2T2T行每2 22行表示1 11组数据每组数据第1 11行1 11个正整数n nn表示模型个数。每组数据第2 22行n nn个正整数s 1 , s 2 , ⋯ , s n s_1,s_2,⋯,s_ns1,s2,⋯,sn表示模型尺寸。【输出】输出T TT行每行输出一个整数表示每组数据的答案。【输入样例】4 4 5 3 4 6 7 1 4 2 3 6 4 9 5 5 4 3 2 1 1 9【输出样例】2 3 1 1【算法标签】#线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;// 最大模型数量intT,n;// T: 测试数据组数, n: 模型个数ints[N];// s[i]: 第i个模型的尺寸intdp[N];// dp[i]: 以第i个模型结尾的满足条件的最长序列长度intmain(){cinT;// 读入测试数据组数while(T--)// 依次处理每组数据{cinn;// 读入模型个数// 读入每个模型的尺寸for(inti1;in;i)cins[i];// 初始化每个模型单独构成长度为1的序列for(inti1;in;i)dp[i]1;intans1;// 答案至少可以购买1个模型// 动态规划枚举每个模型作为序列结尾for(inti1;in;i){// 枚举i的所有因子jj i检查是否能从j转移过来// 优化只枚举到sqrt(i)同时处理因子j和配对因子i/jfor(intj1;j*ji;j){if(i%j0)// j是i的因子{// 情况1j是i的因子且j i// 条件编号j是i的因子即i是j的倍数且尺寸严格递增if(s[j]s[i])dp[i]max(dp[i],dp[j]1);// 情况2i/j也是i的因子j的配对因子intotheri/j;// 避免重复计算当j*ji时otherj跳过// 条件other i且尺寸严格递增if(other!js[other]s[i])dp[i]max(dp[i],dp[other]1);}}ansmax(ans,dp[i]);// 更新全局最大值}coutansendl;// 输出当前测试数据的答案}return0;}【运行结果】4 4 5 3 4 6 2 7 1 4 2 3 6 4 9 3 5 5 4 3 2 1 1 1 9 1
题解：学而思编程 购买模型
发布时间：2026/6/25 14:39:41
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】学而思编程购买模型【题目描述】商店里有n nn个模型编号为1 ∼ n 1∼n1∼n第i ii个模型的尺寸为s i s_isi。小猴想要购买若干个模型他对购买的模型有以下要求1编号从小到大排序后对所有相邻的模型后一个的编号是前一个的倍数。2编号从小到大排序后对所有相邻的模型后一个的尺寸严格大于前一个的尺寸。我们认为只购买1 11个模型也满足要求。例如有6 66个模型大小是[ 3 , 6 , 7 , 3 , 7 , 7 ] [3,6,7,3,7,7][3,6,7,3,7,7]那么小猴可以买第1 , 2 , 6 1,2,61,2,6个模型它们的尺寸是 $[3,6,7]但是小猴不可以购买第1 , 2 , 3 1,2,31,2,3个因为编号3 33不是它前一个编号2 22的倍数小猴也不可以购买第1 , 2 , 4 1,2,41,2,4个因为这三个的尺寸[ 3 , 6 , 3 ] [3,6,3][3,6,3]不是严格升序。小猴想知道他最多可以购买多少个模型。输入包含多组数据。【输入】第1 11行1 11个正整数T TT表示有T TT组数据。接下来2 T 2T2T行每2 22行表示1 11组数据每组数据第1 11行1 11个正整数n nn表示模型个数。每组数据第2 22行n nn个正整数s 1 , s 2 , ⋯ , s n s_1,s_2,⋯,s_ns1,s2,⋯,sn表示模型尺寸。【输出】输出T TT行每行输出一个整数表示每组数据的答案。【输入样例】4 4 5 3 4 6 7 1 4 2 3 6 4 9 5 5 4 3 2 1 1 9【输出样例】2 3 1 1【算法标签】#线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;// 最大模型数量intT,n;// T: 测试数据组数, n: 模型个数ints[N];// s[i]: 第i个模型的尺寸intdp[N];// dp[i]: 以第i个模型结尾的满足条件的最长序列长度intmain(){cinT;// 读入测试数据组数while(T--)// 依次处理每组数据{cinn;// 读入模型个数// 读入每个模型的尺寸for(inti1;in;i)cins[i];// 初始化每个模型单独构成长度为1的序列for(inti1;in;i)dp[i]1;intans1;// 答案至少可以购买1个模型// 动态规划枚举每个模型作为序列结尾for(inti1;in;i){// 枚举i的所有因子jj i检查是否能从j转移过来// 优化只枚举到sqrt(i)同时处理因子j和配对因子i/jfor(intj1;j*ji;j){if(i%j0)// j是i的因子{// 情况1j是i的因子且j i// 条件编号j是i的因子即i是j的倍数且尺寸严格递增if(s[j]s[i])dp[i]max(dp[i],dp[j]1);// 情况2i/j也是i的因子j的配对因子intotheri/j;// 避免重复计算当j*ji时otherj跳过// 条件other i且尺寸严格递增if(other!js[other]s[i])dp[i]max(dp[i],dp[other]1);}}ansmax(ans,dp[i]);// 更新全局最大值}coutansendl;// 输出当前测试数据的答案}return0;}【运行结果】4 4 5 3 4 6 2 7 1 4 2 3 6 4 9 3 5 5 4 3 2 1 1 1 9 1
