本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing4554. 老鼠排队 - AcWing题库【题目描述】给定你若干只老鼠每只老鼠的重量和速度已知。请你从中挑选一些老鼠排成一队要求队伍中的老鼠从前到后体重严格递增。队伍中的老鼠从前到后速度严格递减。队伍中的老鼠数量尽可能多。请你输出满足条件的一支队伍。【输入】输入包含若干行每行包含两个整数w i , s i w_i,s_iwi​,si​表示其中一只老鼠的重量和速度。输入的老鼠按照输入顺序依次编号为1 , 2 , 3 … 1,2,3…1,2,3…。【输出】第一行包含整数n nn表示你挑出的老鼠数量。按照排好队伍后队伍中从前往后的顺序依次输出队伍中每只老鼠的编号每行一个。如果方案不唯一则输出任意合理方案均可。【输入样例】6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900【输出样例】4 4 5 9 7【算法标签】#线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;constintN10005;intcur,ans;// cur: 老鼠数量ans: 最长序列长度structNode{intW,S,idx;// 重量速度原始编号}a[N];intf[N];// f[i]: 以第i只老鼠结尾的最长序列长度intpre[N],endp;// pre[i]: 前驱节点endp: 最长序列的末尾老鼠编号// 比较函数按重量升序排序boolcmp(Node x,Node y){returnx.Wy.W;}// 递归输出最长序列voidprint_path(intx){if(x0)// 如果前驱为0表示到达序列开头return;print_path(pre[x]);// 递归输出前一个老鼠couta[x].idxendl;// 输出当前老鼠的原始编号}intmain(){cur;// 从1开始计数// 读取输入直到文件结束while(~scanf(%d%d,a[cur].W,a[cur].S)){a[cur].idxcur;// 保存原始编号cur;}cur--;// 减去多余的计数// 按重量升序排序sort(a1,acur1,cmp);f[1]1;// 初始化以第一只老鼠结尾的序列长度为1for(inti2;icur;i)// 遍历所有老鼠{intmaxn0;// 记录满足条件的最长序列长度for(intj1;ji;j)// 检查之前的所有老鼠{// 条件重量严格递增速度严格递减if(a[j].Wa[i].Wa[j].Sa[i].S){if(maxnf[j])// 找到更长的序列{maxnf[j];// 更新最大长度pre[i]j;// 记录前驱}}}f[i]maxn1;// 当前老鼠可以接在最长序列后面if(ansf[i])// 更新全局最长序列{ansf[i];// 更新最长序列长度endpi;// 记录最长序列的末尾老鼠编号}}// 调试输出// for (int i1; icur; i)// cout f[i] ;// cout endl;coutansendl;// 输出最长序列长度print_path(endp);// 输出最长序列的所有老鼠编号return0;}【运行结果】6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900 4 4 5 9 7