本文分享的必刷题目是从蓝桥云课、洛谷、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-一维
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=100005;// 最大模型数量intT,n;// T: 测试数据组数, n: 模型个数ints[N];// s[i]: 第i个模型的尺寸intdp[N];// dp[i]: 以第i个模型结尾的满足条件的最长序列长度intmain(){cin>>T;// 读入测试数据组数while(T--)// 依次处理每组数据{cin>>n;// 读入模型个数// 读入每个模型的尺寸for(inti=1;i<=n;i++)cin>>s[i];// 初始化：每个模型单独构成长度为1的序列for(inti=1;i<=n;i++)dp[i]=1;intans=1;// 答案：至少可以购买1个模型// 动态规划：枚举每个模型作为序列结尾for(inti=1;i<=n;i++){// 枚举i的所有因子j（j < i），检查是否能从j转移过来// 优化：只枚举到sqrt(i)，同时处理因子j和配对因子i/jfor(intj=1;j*j<=i;j++){if(i%j==0)// j是i的因子{// 情况1：j是i的因子，且j < i// 条件：编号j是i的因子（即i是j的倍数），且尺寸严格递增if(s[j]<s[i])dp[i]=max(dp[i],dp[j]+1);// 情况2：i/j也是i的因子（j的配对因子）intother=i/j;// 避免重复计算（当j*j=i时，other==j，跳过）// 条件：other < i，且尺寸严格递增if(other!=j&&s[other]<s[i])dp[i]=max(dp[i],dp[other]+1);}}ans=max(ans,dp[i]);// 更新全局最大值}cout<<ans<<endl;// 输出当前测试数据的答案}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
