本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P2690 [USACO04NOV] Apple Catching G【题目描述】很少有人知道奶牛爱吃苹果。农夫约翰的农场上有两棵苹果树编号为1 11和2 22 每一棵树上都长满了苹果。奶牛贝茜无法摘下树上的苹果所以她只能等待苹果 从树上落下。但是由于苹果掉到地上会摔烂贝茜必须在半空中接住苹果没有人爱吃摔烂的苹果。贝茜吃东西很快她接到苹果后仅用几秒钟就能吃完。每一分钟两棵苹果树其中的一棵会掉落一个苹果。贝茜已经过了足够的训练 只要站在树下就一定能接住这棵树上掉落的苹果。同时贝茜能够在两棵树之间 快速移动移动时间远少于1 11分钟因此当苹果掉落时她必定站在两棵树其中的一棵下面。此外奶牛不愿意不停地往返于两棵树之间因此会错过一些苹果。苹果每分钟掉落一个共T TT1 ≤ T ≤ 1000 1 \le T \le 10001≤T≤1000分钟贝茜最多愿意移动W WW1 ≤ W ≤ 30 1 \le W \le 301≤W≤30 次。现给出每分钟掉落苹果的树的编号要求判定贝茜能够接住的最多苹果数。 开始时贝茜在 1 号树下。【输入】第一行2 22个数T TT和W WW。接下来的t tt行每行一个数代表在时刻t tt苹果是从1 11号苹果树还是从2 22号苹果树上掉下来的。【输出】对于每个测试点输出一行一个数为奶牛最多接到的苹果的数量。【输入样例】7 2 2 1 1 2 2 1 1【输出样例】6【核心思想】问题分析给定T TT分钟内每分钟苹果掉落的树编号a i ∈ { 1 , 2 } a_i \in \{1, 2\}ai​∈{1,2}贝茜初始在1 11号树下最多移动W WW次。每分钟若贝茜所在树下有苹果掉落即可接住。求最多能接住的苹果数。这是一个线性 DP问题关键在于状态设计需同时记录时间、已用移动次数和当前位置。算法选择线性 DP一维扩展按时间顺序递推状态包含已用移动次数和当前位置两个维度状态转移每分钟有两种选择——留在原地不消耗移动次数或从另一棵树移动过来消耗1 11次移动次数关键步骤初始化读取T TT总分钟数、W WW最大移动次数、a [ 1.. T ] a[1..T]a[1..T]每分钟掉落苹果的树编号DP 状态定义f [ i ] [ j ] [ k ] f[i][j][k]f[i][j][k]表示前i ii分钟移动了j jj次当前在树k 1 k1k1下k 0 k0k0表示树1 11k 1 k1k1表示树2 22接到的最多苹果数初始状态f [ 0 ] [ 0 ] [ 0 ] 0 f[0][0][0] 0f[0][0][0]0第0 00分钟在树1 11下移动0 00次接到0 00个其余状态为− ∞ -\infty−∞状态转移遍历i ii从1 11到T TTj jj从0 00到W WW不移动f [ i ] [ j ] [ 0 ] f [ i − 1 ] [ j ] [ 0 ] ( a i 1 ) f[i][j][0] f[i-1][j][0] (a_i 1)f[i][j][0]f[i−1][j][0](ai​1)f [ i ] [ j ] [ 1 ] f [ i − 1 ] [ j ] [ 1 ] ( a i 2 ) f[i][j][1] f[i-1][j][1] (a_i 2)f[i][j][1]f[i−1][j][1](ai​2)移动过来需j ≥ 1 j \geq 1j≥1从树2 22移到树1 11f [ i ] [ j ] [ 0 ] max ⁡ ( f [ i ] [ j ] [ 0 ] , f [ i − 1 ] [ j − 1 ] [ 1 ] ( a i 1 ) ) f[i][j][0] \max(f[i][j][0], f[i-1][j-1][1] (a_i 1))f[i][j][0]max(f[i][j][0],f[i−1][j−1][1](ai​1))从树1 11移到树2 22f [ i ] [ j ] [ 1 ] max ⁡ ( f [ i ] [ j ] [ 1 ] , f [ i − 1 ] [ j − 1 ] [ 0 ] ( a i 2 ) ) f[i][j][1] \max(f[i][j][1], f[i-1][j-1][0] (a_i 2))f[i][j][1]max(f[i][j][1],f[i−1][j−1][0](ai​2))统计答案a n s max ⁡ 0 ≤ j ≤ W , k ∈ { 0 , 1 } f [ T ] [ j ] [ k ] ans \max_{0 \leq j \leq W, k \in \{0,1\}} f[T][j][k]ansmax0≤j≤W,k∈{0,1}​f[T][j][k]时间/空间复杂度时间复杂度O ( T × W ) O(T \times W)O(T×W)双层循环每层内部O ( 1 ) O(1)O(1)转移空间复杂度O ( T × W ) O(T \times W)O(T×W)三维 DP 数组可滚动优化至O ( W ) O(W)O(W)线性 DP 的核心思想时间维度递推按时间顺序处理每分钟的状态仅依赖于前一分钟的状态满足无后效性状态设计技巧将当前位置和已用资源移动次数纳入状态将复杂的决策过程转化为状态转移选择建模每个时刻只有不动和移动两种决策分别对应不同的前置状态取最大值保证最优性边界处理初始位置固定在树1 11通过f [ 0 ] [ 0 ] [ 0 ] 0 f[0][0][0] 0f[0][0][0]0和其余− ∞ -\infty−∞确保状态合法性适用于有时间序列约束、资源限制如移动次数的最优化问题【算法标签】#普及 #线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;constintN1005;// 最大时间上限intt,w,ans-1;// t:总分钟数, w:最大移动次数, ans:最多接住的苹果数inta[N];// a[i]:第i分钟苹果从哪棵树掉落1或2intf[N][35][2];// f[i][j][k]:前i分钟移动了j次当前在树k1下接到的最多苹果数intmain(){cintw;// 读入总时间和最大移动次数for(inti1;it;i)// 读入每分钟苹果掉落的树编号cina[i];// 初始化DP数组为负无穷表示不可达状态memset(f,-0x3f,sizeof(f));f[0][0][0]0;// 初始状态第0分钟在1号树下移动0次接到0个苹果for(inti1;it;i)// 外层循环枚举每一分钟for(intj0;jw;j)// 中层循环枚举已使用的移动次数{// 情况1不移动继续留在当前树下// 留在1号树下如果当前苹果从1号树掉落则接住f[i][j][0]f[i-1][j][0](a[i]1);// 留在2号树下如果当前苹果从2号树掉落则接住f[i][j][1]f[i-1][j][1](a[i]2);// 情况2从另一棵树移动过来消耗一次移动机会// 从2号树移动到1号树如果当前苹果从1号树掉落则接住if(j1)f[i][j][0]max(f[i][j][0],f[i-1][j-1][1](a[i]1));// 从1号树移动到2号树如果当前苹果从2号树掉落则接住if(j1)f[i][j][1]max(f[i][j][1],f[i-1][j-1][0](a[i]2));}// 枚举所有可能的移动次数和最终位置取最大值for(intj0;jw;j)ansmax({ans,f[t][j][0],f[t][j][1]});coutansendl;// 输出最多接住的苹果数return0;}【运行结果】7 2 2 1 1 2 2 1 1 6