本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderE - Minimum Cost of Stepping Stones【题目描述】Takahashi is trying to cross a river. There areN NNstepping stones lined up in a row in the river, numbered stone1 11, stone2 22,… \ldots…, stoneN NNin order from the left bank. Takahashi starts on stone1 11and reaches the goal when he arrives at stoneN NN.高桥正试图渡过一条河。河中有N NN块踏脚石排成一行从左岸开始依次编号为石头1 11、石头2 22、……、石头N NN。高桥从石头1 11出发当他到达石头N NN时即到达目标。From his current stonei ii, Takahashi can jump to any one of stonei 1 i1i1, stonei 2 i2i2,… \ldots…, stonemin ⁡ ( i K , N ) \min(iK,\, N)min(iK,N). In other words, the difference in stone numbers covered in a single jump is between1 11andK KKinclusive, and he can only move in the direction of increasing numbers. Takahashi must land exactly on stoneN NNat the end.从当前所在的石头i ii高桥可以跳到石头i 1 i1i1、石头i 2 i2i2、……、石头min ⁡ ( i K , N ) \min(iK,\, N)min(iK,N)中的任意一块。换句话说单次跳跃跨越的石头编号差在1 11到K KK之间含端点且他只能朝编号增加的方向移动。高桥最终必须恰好落在石头N NN上。Each stepping stonei ii( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N)has a positive integer valueA i A_iAi​assigned to it. When Takahashi lands on a stone, that stone’s value is added to the cumulative cost. The values of stones he does not land on are not added. The valueA 1 A_1A1​of the starting stone1 11and the valueA N A_NAN​of the goal stoneN NNare also each added when he lands on them.每块踏脚石i ii1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N都有一个正整数A i A_iAi​作为其值。当高桥落在一块石头上时该石头的值会被累加到累计成本中。他没有踩到的石头的值不会被累加。起始石头1 11的值A 1 A_1A1​和目标石头N NN的值A N A_NAN​也会在他落在上面时分别被累加。Among all paths Takahashi can take from stone1 11to stoneN NN, find the one that minimizes the cumulative cost, and output that minimum cumulative cost.在高桥从石头1 11到石头N NN的所有可行路径中找出使累计成本最小化的路径并输出该最小累计成本。【输入】N NNK KKA 1 A_1A1​A 2 A_2A2​… \ldots…A N A_NAN​The first line contains an integerN NNrepresenting the number of stepping stones and an integerK KKrepresenting the maximum difference in stone numbers that can be covered in a single jump, separated by a space.The second line contains integersA 1 , A 2 , … , A N A_1, A_2, \ldots, A_NA1​,A2​,…,AN​representing the values of each stepping stone, separated by spaces.【输出】Output in one line the minimum cumulative cost when traveling from stone1 11to stoneN NN.【输入样例】5 2 1 3 2 4 1【输出样例】4【解题思路】【算法标签】#单调队列#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN1000005,INF1e18;intn,k;inta[N],dp[N];// a: 代价数组, dp: 动态规划数组structNode{intv,idx;// v: 值, idx: 索引};dequeNodedq;// 单调队列signedmain(){scanf(%d %d,n,k);// 输入数组长度和跳跃距离限制for(inti1;in;i){scanf(%d,a[i]);// 输入每个位置的代价}for(inti1;in;i)// 初始化dp数组{dp[i]INF;}dp[1]a[1];// 起点代价dq.push_back({dp[1],1});// 将起点加入队列for(inti2;in;i){// 移除超出窗口范围的元素while(!dq.empty()dq.front().idxi-k){dq.pop_front();}// 转移方程dp[i] min{dp[j]} a[i] (i-k ≤ j i)dp[i]dq.front().va[i];// 维护队列单调递增while(!dq.empty()dq.back().vdp[i]){dq.pop_back();}dq.push_back({dp[i],i});// 将当前元素加入队列}coutdp[n]endl;// 输出到达终点的最小总代价return0;}【运行结果】5 2 1 3 2 4 1