企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、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 + 31+3，删去2 22后a = [ 1 , 3 ] a = [1, 3]a=[1,3]；
• 指定元素1 11，获得分数0 + 3 0 + 30+3，删去1 11后a = [ 3 ] a = [3]a=[3]；
• 指定元素3 33，获得分数0 + 0 0 + 00+0，删去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

【核心思想】

1. 问题分析：给定数组a 1 , a 2 , … , a n a_1, a_2, \ldots, a_na1​,a2​,…,an​，每次删除一个元素获得其两侧相邻元素之和的分数，求删除所有元素的最大分数总和。这是一个区间动态规划问题，核心在于分析删除顺序对得分的影响——最后删除的元素在得分时其相邻元素是固定的区间外边界。

2. 算法选择：

   • 区间 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_{j+1}aj+1​（区间外的边界元素），得分固定

3. 关键步骤：

   • 边界处理：a 0 = 0 a_0 = 0a0​=0，a n + 1 = 0 a_{n+1} = 0an+1​=0，作为虚拟边界
   • 初始化（区间长度为1 11）：d p [ i ] [ i ] = a i − 1 + a i + 1 dp[i][i] = a_{i-1} + a_{i+1}dp[i][i]=ai−1​+ai+1​，删除单个元素i ii时得分为其两侧相邻元素之和
   • 区间 DP（l e n lenlen从2 22到n nn）：
     • 枚举左端点i ii，计算右端点j = i + l e n − 1 j = i + len - 1j=i+len−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[k+1][j] + a_{i-1} + a_{j+1})dp[i][j]=max(dp[i][j],dp[i][k−1]+dp[k+1][j]+ai−1​+aj+1​)
     • 解释：先分别删除[ i , k − 1 ] [i, k-1][i,k−1]和[ k + 1 , j ] [k+1, j][k+1,j]内的元素，最后删除k kk，此时k kk的相邻元素为a i − 1 a_{i-1}ai−1​和a j + 1 a_{j+1}aj+1​
   • 输出结果：d p [ 1 ] [ n ] dp[1][n]dp[1][n]

4. 时间/空间复杂度：

   • 时间复杂度：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数组

5. 区间动态规划的核心思想：

   • 最后删除的确定性：对于区间[ i , j ] [i, j][i,j]，无论内部删除顺序如何，最后一个被删除的元素k kk在得分时，其相邻元素一定是a i − 1 a_{i-1}ai−1​和a j + 1 a_{j+1}aj+1​。这是因为[ i , j ] [i, j][i,j]内其他元素已被删除，k kk的左右邻居就是区间边界外的元素
   • 子问题独立性：删除[ i , k − 1 ] [i, k-1][i,k−1]和[ k + 1 , j ] [k+1, j][k+1,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[k+1][j]dp[k+1][j]已经计算完成
   • 边界元素的固定贡献：最后删除k kk的得分a i − 1 + a j + 1 a_{i-1} + a_{j+1}ai−1​+aj+1​与k kk的具体值无关，只与区间边界有关，这是状态转移的关键
   • 适用于元素删除顺序影响得分、且最后操作的相邻元素具有确定性特征的区间优化类问题

【算法标签】

#普及 #区间DP

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=105;// 常量：最大数组长度intn;// n: 数组长度inta[N];// a[i]: 数组元素，a[0] 和 a[n+1] 视为边界（值为0）intdp[N][N];// dp[i][j]: 删除区间 [i,j] 内所有元素能获得的最大分数signedmain(){cin>>n;// 读入数组长度for(inti=1;i<=n;i++)// 读入数组元素cin>>a[i];for(inti=1;i<=n;i++)// 初始化：区间长度为 1 的情况dp[i][i]=a[i-1]+a[i+1];// 删除单个元素 i，得分 = 左侧相邻 + 右侧相邻for(intlen=2;len<=n;len++)// 枚举区间长度，从 2 到 nfor(inti=1;i+len-1<=n;i++)// 枚举区间左端点{intj=i+len-1;// j: 区间右端点for(intk=i;k<=j;k++)// 枚举区间内最后一个被删除的元素 k{// 状态转移：先删除 [i,k-1] 和 [k+1,j] 内的元素，最后删除 k// 最后删除 k 时，其相邻元素为 a[i-1] 和 a[j+1]（区间外的边界元素）dp[i][j]=max(dp[i][j],dp[i][k-1]+dp[k+1][j]+a[i-1]+a[j+1]);}}cout<<dp[1][n]<<endl;// 输出删除整个数组 [1,n] 的最大分数return0;}

【运行结果】

6 1 6 3 2 9 1 55