区间DP第3课：区间DP应用案例实践2-开发者社区

区间DP第3课：区间DP应用案例实践2

题目描述

有N NN个不同的正整数x 1 x_1x1,x 2 x_2x2, …,x N x_NxN排成一排，我们可以从左边或右边去掉连续的i ii( 1 ≤ i ≤ n ) (1 \le i \le n)(1≤i≤n)个数（只能从两边删除数），剩下N − i N-iN−i个数，再把剩下的数按以上操作处理，直到所有的数都被删除为止。

每次操作都有一个操作价值，比如现在要删除从i ii位置到k kk位置上的所有的数。操作价值为∣ x i − x k ∣ × ( k − i + 1 ) |x_i-x_k| \times (k-i+1)∣xi−xk∣×(k−i+1)，如果只去掉一个数，操作价值为这个数的值。
问如何操作可以得到最大值，求操作的最大价值。

输入格式

第一行为一个正整数N NN;

第二行有N NN个用空格隔开的N NN个不同的正整数。

输出格式

一行，包含一个正整数，为操作的最大值

输入输出样例 1

输入 1

6 54 29 196 21 133 118

输出 1

说明/提示

【样例解释和说明】

说明，经过3 33次操作可以得到最大值，第一次去掉前面3 33个数：54 5454、29 2929、196 196196，操作价值为426 426426。第二次操作是在剩下的三个数( 21 , 133 , 118 ) (21,133,118)(21,133,118)中去掉最后一个数118 118118，操作价值为118 118118。第三次操作去掉剩下的2 22个数：21 2121和133 133133，操作价值为224 224224。操作总价值为426 + 118 + 224 = 768 426+118+224=768426+118+224=768。

【数据范围】

3 ≤ N ≤ 100 3≤N≤1003≤N≤100，1 ≤ x i ≤ 1000 1 \le x_i \le 10001≤xi≤1000

方法思路

状态定义：定义dp[i][j]为删除从位置i到j的所有数字所能获得的最大价值。
初始状态：当区间长度为1时，即i == j，此时的价值就是这个数字本身的值。
状态转移：对于每个区间[i, j]，我们有两种选择：
- 直接删除整个区间，其价值为abs(a[i] - a[j]) * (j - i + 1)。
- 将区间分割成两个子区间[i, k]和[k+1, j]，并取这两个子区间价值的和的最大值。
递推顺序：按区间长度从小到大处理，逐步计算每个区间的最大价值。

解决代码

#include<bits/stdc++.h>usingnamespacestd;intn;intdp[110][110];intmain(){cin>>n;for(inti=1;i<=n;i++){cin>>a[i];}// 初始化长度为1的区间for(inti=1;i<=n;i++){dp[i][i]=a[i];}// 枚举区间长度for(intlen=2;len<=n;len++){for(inti=1;i+len-1<=n;i++){intj=i+len-1;// 计算直接删除整个区间的价值intval=abs(a[i]-a[j])*len;// 计算分割后的最大值intmax_split=0;for(intk=i;k<j;k++){max_split=max(max_split,dp[i][k]+dp[k+1][j]);}dp[i][j]=max(val,max_split);}}cout<<dp[1][n]<<endl;return0;}

代码解释

输入处理：读取输入的整数n和数组a。
初始化：将所有长度为1的区间的最大价值初始化为该位置的值。
动态规划计算：按区间长度从小到大，逐步计算每个区间的最大价值。对于每个区间，计算直接删除整个区间的价值和分割后的子区间价值之和的最大值，并更新当前区间的最大价值。
输出结果：最终结果存储在dp[1][n]中，表示整个数组的最大操作价值。

完整系列资料，请查看专栏：《csp信奥赛C++动态规划》
https://blog.csdn.net/weixin_66461496/category_13096895.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

2025 csp-j 复赛真题及答案解析（最新更新）
2025 csp-x(山东) 复赛真题及答案解析（最新更新）
2025 csp-x(河南) 复赛真题及答案解析（最新更新）
2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
2025 csp-x(江西) 复赛真题及答案解析（最新更新）
2025 csp-x(广西) 复赛真题及答案解析（最新更新）
2020 ~ 2024 csp 复赛真题题单及题解
2019 ~ 2022 csp-j 初赛高频考点真题分类解析
2021 ~ 2024 csp-s 初赛高频考点解析
2023 ~ 2024 csp-x (山东)初赛真题及答案解析
2024 csp-j 初赛真题及答案解析
2025 csp-j 初赛真题及答案解析（最新更新）
2025 csp-s 初赛真题及答案解析（最新更新）
2025 csp-x (山东)初赛真题及答案解析(最新更新)
2025 csp-x (江西)初赛真题及答案解析(最新更新)
2025 csp-x (辽宁)初赛真题及答案解析(最新更新)

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、前缀和、差分、深搜、广搜、DP专题、树和图

4、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

区间DP第3课：区间DP应用案例实践2