本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P17015 [GESP202606 七级] 消消乐 - 洛谷【题目描述】给定一个由n nn个整数构成的数组a [ a 1 , … , a n ] a [a_1, \ldots, a_n]a[a1​,…,an​]。每次你可以对数组a aa进行以下操作直到数组a aa变为空指定a aa中的一个元素获得该元素两侧相邻元素之和的分数并将该元素从a aa中删去。特别地如果相邻元素不存在则该元素的值视为0 00。例如对于a [ 1 , 2 , 3 ] a [1, 2, 3]a[1,2,3]可以进行以下操作指定元素2 22获得分数1 3 1 313删去2 22后a [ 1 , 3 ] a [1, 3]a[1,3]指定元素1 11获得分数0 3 0 303删去1 11后a [ 3 ] a [3]a[3]指定元素3 33获得分数0 0 0 000删去3 33后a aa变为空。请问你能获得的分数总和最大是多少【输入】第一行一个正整数n nn表示数组长度。第二行n nn个非负整数a 1 , … , a n a_1, \ldots, a_na1​,…,an​表示数组a aa中的整数。【输出】输出一行一个整数表示能获得的最大分数总和。【输入样例】6 1 6 3 2 9 1【输出样例】55【核心思想】问题分析给定数组a 1 , a 2 , … , a n a_1, a_2, \ldots, a_na1​,a2​,…,an​每次删除一个元素获得其两侧相邻元素之和的分数求删除所有元素的最大分数总和。这是一个区间动态规划问题核心在于分析删除顺序对得分的影响——最后删除的元素在得分时其相邻元素是固定的区间外边界。算法选择区间 DP设d p [ i ] [ j ] dp[i][j]dp[i][j]为删除区间[ i , j ] [i, j][i,j]内所有元素能获得的最大分数最后删除策略枚举区间[ i , j ] [i, j][i,j]内最后一个被删除的元素k kk此时k kk的相邻元素为a i − 1 a_{i-1}ai−1​和a j 1 a_{j1}aj1​区间外的边界元素得分固定关键步骤边界处理a 0 0 a_0 0a0​0a n 1 0 a_{n1} 0an1​0作为虚拟边界初始化区间长度为1 11d p [ i ] [ i ] a i − 1 a i 1 dp[i][i] a_{i-1} a_{i1}dp[i][i]ai−1​ai1​删除单个元素i ii时得分为其两侧相邻元素之和区间 DPl e n lenlen从2 22到n nn枚举左端点i ii计算右端点j i l e n − 1 j i len - 1jilen−1枚举最后删除的元素k ∈ [ i , j ] k \in [i, j]k∈[i,j]d p [ i ] [ j ] max ⁡ ( d p [ i ] [ j ] , d p [ i ] [ k − 1 ] d p [ k 1 ] [ j ] a i − 1 a j 1 ) dp[i][j] \max(dp[i][j], dp[i][k-1] dp[k1][j] a_{i-1} a_{j1})dp[i][j]max(dp[i][j],dp[i][k−1]dp[k1][j]ai−1​aj1​)解释先分别删除[ i , k − 1 ] [i, k-1][i,k−1]和[ k 1 , j ] [k1, j][k1,j]内的元素最后删除k kk此时k kk的相邻元素为a i − 1 a_{i-1}ai−1​和a j 1 a_{j1}aj1​输出结果d p [ 1 ] [ n ] dp[1][n]dp[1][n]时间/空间复杂度时间复杂度O ( n 3 ) O(n^3)O(n3)三层循环区间长度O ( n ) O(n)O(n)、左端点O ( n ) O(n)O(n)、枚举最后删除元素O ( n ) O(n)O(n)空间复杂度O ( n 2 ) O(n^2)O(n2)二维d p dpdp数组区间动态规划的核心思想最后删除的确定性对于区间[ i , j ] [i, j][i,j]无论内部删除顺序如何最后一个被删除的元素k kk在得分时其相邻元素一定是a i − 1 a_{i-1}ai−1​和a j 1 a_{j1}aj1​。这是因为[ i , j ] [i, j][i,j]内其他元素已被删除k kk的左右邻居就是区间边界外的元素子问题独立性删除[ i , k − 1 ] [i, k-1][i,k−1]和[ k 1 , j ] [k1, j][k1,j]是两个独立的子问题互不影响满足最优子结构区间长度递增按区间长度从小到大枚举确保计算d p [ i ] [ j ] dp[i][j]dp[i][j]时所有子区间d p [ i ] [ k − 1 ] dp[i][k-1]dp[i][k−1]和d p [ k 1 ] [ j ] dp[k1][j]dp[k1][j]已经计算完成边界元素的固定贡献最后删除k kk的得分a i − 1 a j 1 a_{i-1} a_{j1}ai−1​aj1​与k kk的具体值无关只与区间边界有关这是状态转移的关键适用于元素删除顺序影响得分、且最后操作的相邻元素具有确定性特征的区间优化类问题【算法标签】#普及 #区间DP【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN105;// 常量最大数组长度intn;// n: 数组长度inta[N];// a[i]: 数组元素a[0] 和 a[n1] 视为边界值为0intdp[N][N];// dp[i][j]: 删除区间 [i,j] 内所有元素能获得的最大分数signedmain(){cinn;// 读入数组长度for(inti1;in;i)// 读入数组元素cina[i];for(inti1;in;i)// 初始化区间长度为 1 的情况dp[i][i]a[i-1]a[i1];// 删除单个元素 i得分 左侧相邻 右侧相邻for(intlen2;lenn;len)// 枚举区间长度从 2 到 nfor(inti1;ilen-1n;i)// 枚举区间左端点{intjilen-1;// j: 区间右端点for(intki;kj;k)// 枚举区间内最后一个被删除的元素 k{// 状态转移先删除 [i,k-1] 和 [k1,j] 内的元素最后删除 k// 最后删除 k 时其相邻元素为 a[i-1] 和 a[j1]区间外的边界元素dp[i][j]max(dp[i][j],dp[i][k-1]dp[k1][j]a[i-1]a[j1]);}}coutdp[1][n]endl;// 输出删除整个数组 [1,n] 的最大分数return0;}【运行结果】6 1 6 3 2 9 1 55