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

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

题目描述

约翰经常给产奶量高的奶牛发特殊津贴，于是很快奶牛们拥有了大笔不知该怎么花的钱。为此，约翰购置了N NN（1 ≤ N ≤ 2000 1 \leq N \leq 20001≤N≤2000） 份美味的零食来卖给奶牛们。每天约翰售出一份零食。当然约翰希望这些零食全部售出后能得到最大的收益，这些零食有以下这些有趣的特性：

• 零食按照1 , … , N 1, \ldots, N1,…,N编号，它们被排成一列放在一个很长的盒子里。盒子的两端都有开口，约翰每天可以从盒子的任一端取出最外面的一个。
• 与美酒与好吃的奶酪相似，这些零食储存得越久就越好吃。当然，这样约翰就可以把它们卖出更高的价钱。
• 每份零食的初始价值不一定相同。约翰进货时，第i份零食的初始价值为V i V_iVi​（1 ≤ V ≤ 1000 1 \leq V \leq 10001≤V≤1000）。
• 第i ii份零食如果在被买进后的第a aa天出售，则它的售价是V i × a V_i \times aVi​×a。

V i V_iVi​是从盒子顶端往下的第i ii份零食的初始价值。约翰告诉了你所有零食的初始价值，并希望你能帮他计算一下，在这些零食全被卖出后，他最多能得到多少钱。

输入格式

第一行一个正整数N NN。

第二行N NN个正整数V 1 ∼ V N V_1 \sim V_NV1​∼VN​。

输出格式

一行一个整数表示答案。

输入输出样例 1

输入 1

5 1 3 1 5 2

输出 1

43

说明/提示

样例的最优解是：按1 → 5 → 2 → 3 → 4 1 \to 5 \to 2 \to 3 \to 41→5→2→3→4的顺序卖零食，得到的钱数是1 × 1 + 2 × 2 + 3 × 3 + 4 × 1 + 5 × 5 = 43 1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 1 + 5 \times 5 = 431×1+2×2+3×3+4×1+5×5=43。

方法思路

1. 问题分析：每次出售零食时，可以选择从队列的头部或尾部取出，因此这是一个典型的区间动态规划问题。我们需要计算每个子区间的最大收益，并逐步合并这些结果来解决整个问题。

2. 动态规划状态定义：定义dp[i][j]表示从第i个到第j个零食的区间内，能获得的最大收益。

3. 状态转移方程：对于每个区间[i, j]，当前出售的天数为a = n - (j - i)，其中n是总天数。我们可以选择出售左端或右端的零食，并取最大收益：

   • 出售左端的收益为v[i] * a + dp[i+1][j]
   • 出售右端的收益为v[j] * a + dp[i][j-1]
     因此，状态转移方程为：dp[i][j] = max(v[i] * a + dp[i+1][j], v[j] * a + dp[i][j-1])

4. 初始化：当区间长度为1时，直接计算该零食在第n天出售的价值。

5. 计算顺序：按区间长度从小到大计算，逐步合并子区间的结果。

解决代码

#include<bits/stdc++.h>intv[2005];intdp[2005][2005];intmain(){intn;cin>>n;for(inti=1;i<=n;i++){cin>>v[i];}// 初始化长度为1的区间for(inti=1;i<=n;i++){dp[i][i]=v[i]*n;}// 处理长度从2到n的区间for(intlen=2;len<=n;len++){for(inti=1;i<=n-len+1;i++){intj=i+len-1;inta=n-(j-i);// 计算当前的天数dp[i][j]=max(v[i]*a+dp[i+1][j],v[j]*a+dp[i][j-1]);}}cout<<dp[1][n]<<endl;return0;}

代码解释

1. 输入处理：读取零食数量n和每个零食的价值v[i]。
2. 初始化：对于每个长度为1的区间[i, i]，其最大收益为当前零食在第n天的价值。
3. 动态规划计算：按区间长度从小到大遍历，计算每个区间的最大收益。对于每个区间[i, j]，计算当前天数a，并根据选择左端或右端的零食更新最大收益。
4. 输出结果：最终结果存储在dp[1][n]中，表示整个区间[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;}