1. 题目回顾「挖矿」是蓝桥杯省赛中的一道经典动态规划题目考察选手对状态定义、状态转移以及边界处理的综合能力。题目大意如下在一个一维的矿脉上有n个矿点每个矿点有一个价值a[i]。矿工从某个起点出发每次可以向左或向右移动一格也可以选择停下。矿工经过的矿点会被开采并获得对应价值每个矿点最多开采一次。给定矿工的最大移动步数m求矿工能获得的最大总价值。题目通常还会附加一个限制矿工只能改变一次方向即先朝一个方向走再掉头朝另一个方向走这使得问题从一般的区间遍历转化为前缀和 枚举转折点的经典模型。2. 思路分析2.1 关键观察本题的模型是矿工从原点 0 出发左右两侧各有若干矿点最多走m步且只能拐一次弯。用r[i]记录右侧距离i处是否有矿l[i]记录左侧距离i处是否有矿做前缀和后r[i] 从原点向右走i步能采到的矿数l[i] 从原点向左走i步能采到的矿数。路径只有两种形态先向右再向左先向右走i步再掉头向左走m - 2i步采到r[i] l[m-2i]先向左再向右对称采到l[i] r[m-2i]。枚举i取最大值最后加上原点是否有矿f即可。2.2 前缀和优化读入矿点时右侧矿点用r[pos]记录左侧矿点用l[abs(pos)]记录原点用f 1标记。随后做前缀和for(inti1;im;i){r[i]r[i-1];l[i]l[i-1];}这样r[i]就表示从原点向右走i步能采到的矿数l[i]同理。2.3 枚举转折点对于「先向右再向左」枚举向右走的步数i掉头后向左还能走m - 2i步总收获为r[i] l[m-2i]。注意只有当m - 2i 0时才累加否则会访问负数下标导致数组越界。「先向左再向右」完全对称枚举i后累加l[i] r[m-2i]即可。3. C 代码实现#includebits/stdc.husingnamespacestd;constintN1e610;intl[N],r[N];intmain(){intf0;intn,m,ans0;cinnm;for(inti0;in;i){intpos;cinpos;if(pos0){r[pos];}if(pos0){l[abs(pos)];}if(pos0){f1;}}l[0]0,r[0]0;// 前缀和r[i] 从原点向右走 i 步能采到的矿数for(inti1;im;i){r[i]r[i-1];l[i]l[i-1];}// 形态 1先向右走 i 步再掉头向左走 m - 2i 步for(inti1;im;i){intsum1r[i];if(m-2*i0){sum1l[m-2*i];ansmax(ans,sum1);}}// 形态 2先向左走 i 步再掉头向右走 m - 2i 步for(inti1;im;i){intsum1l[i];if(m-2*i0){sum1r[m-2*i];ansmax(ans,sum1);}}coutansf;return0;}4. 复杂度分析时间复杂度O(m)只需枚举转折点配合前缀和O(1)查询区间和。空间复杂度O(m)用于存储左右两侧的前缀和数组。相比朴素O(n^2)的区间枚举前缀和 枚举转折点的做法在n 10^5的数据范围内可以轻松通过。5. 易错点与注意事项掉头步数 m - 2i掉头点会被走两次所以反方向的净步数是m - 2i不是m - i。负数下标防护当m - 2i 0时说明步数不够走到i再掉头此时l[m-2i]会访问负数下标导致数组越界所以代码里用if (m - 2 * i 0)判断后才累加。原点单独加前缀和r[i]、l[i]都不含原点最后要ans f补上。数组大小N至少要开到m 5避免m较大时越界。abs(pos)取绝对值左侧矿点用l[abs(pos)]记录注意abs需要cstdlibbits/stdc.h已包含。6. 总结蓝桥杯「挖矿」是一道典型的动态规划入门题核心在于识别出「最多改变一次方向」这一关键限制用左右两个前缀和数组r[i]、l[i]快速统计各方向能采到的矿数枚举转折点掉头步数为m - 2i注意负数下标防护最后补上原点f整体复杂度O(m)。建议读者在理解代码后自己动手在纸上模拟一遍小数据加深对步数计算和边界处理的理解。7. 附对「从原点出发」代码实现的分析有读者提交了另一种实现其模型是矿工从原点 0 出发左右两侧各有若干矿点最多走m步且只能拐一次弯。这种写法与上文「从任意起点s出发」的模型不同但更贴近部分原题设定思路同样正确这里单独分析。7.1 核心思路用r[i]记录右侧距离i处是否有矿l[i]记录左侧距离i处是否有矿做前缀和后r[i] 从原点向右走i步能采到的矿数l[i] 从原点向左走i步能采到的矿数。路径只有两种形态先向右再向左先向右走i步再掉头向左走m - 2i步采到r[i] l[m-2i]先向左再向右对称采到l[i] r[m-2i]。枚举i取最大值最后加上原点是否有矿f即可。7.2 关键细节与易错点掉头步数 m - 2i掉头点会被走两次所以反方向的净步数是m - 2i不是m - i。负数下标防护当m - 2i 0时说明步数不够走到i再掉头此时l[m-2i]会访问负数下标导致数组越界所以代码里用if (m - 2 * i 0)判断后才累加。原点单独加前缀和r[i]、l[i]都不含原点最后要ans f补上。数组大小N至少要开到m 5避免m较大时越界。abs(pos)取绝对值左侧矿点用l[abs(pos)]记录注意abs需要cstdlibbits/stdc.h已包含。7.3 修正后的参考代码#includebits/stdc.husingnamespacestd;constintN1e610;intl[N],r[N];intmain(){intf0;intn,m,ans0;cinnm;for(inti0;in;i){intpos;cinpos;if(pos0){r[pos];}if(pos0){l[abs(pos)];}if(pos0){f1;}}l[0]0,r[0]0;// 前缀和r[i] 从原点向右走 i 步能采到的矿数for(inti1;im;i){r[i]r[i-1];l[i]l[i-1];}// 形态 1先向右走 i 步再掉头向左走 m - 2i 步for(inti1;im;i){intsum1r[i];if(m-2*i0){sum1l[m-2*i];ansmax(ans,sum1);}}// 形态 2先向左走 i 步再掉头向右走 m - 2i 步for(inti1;im;i){intsum1l[i];if(m-2*i0){sum1r[m-2*i];ansmax(ans,sum1);}}coutansf;return0;}这种「从原点出发 左右前缀和」的写法复杂度同样是O(m)代码更简洁但要注意数组越界和掉头步数计算这两个细节。