【7.21-26】代码源 - 【体育节】【丹钓战】【最大权值划分】

#668. 体育节

题意：给定序列，你需要重排列序列，使得序列的前缀极值差的和最小，输出这个最小值。$(n\le 2000)$

题解：(区间dp) 代码源每日一题 Div1 体育节

思路：我们思考一下，现在有一个排好的序列，我们插入一个会成为序列极值的元素，那么放在哪里贡献最小？是放在最后。因为如果放在中间，会影响后面前缀的极值差。对于不会成为序列极值的元素，我们不考虑插入策略。

那么我们排一下序，从每个点向外扩展，扩展到的一定是极值点。定义 $dp(i,j)$ 为区间 $[i,j]$ 的最小前缀极值差和，采用向外拓展的区间 DP， $dp(i,j)=a_j-a_i+\max (dp(i+1,j),dp(i,j-1))$

一些区间 DP 的题（枚举中断点，以及区间合并）：区间dp

AC代码：http://oj.daimayuan.top/submission/299976

---

#702. 丹钓战

题意：$(n,q\le 5\times 10^5)$

题解：(单调栈/树状数组)代码源每日题意 Div1 丹钓战

思路：因为一个元素是好的当且仅当扫描后栈中仅有一个元素。那么我们模拟一下，然后处理出来栈扫到每个元素之后，栈顶的次元素下标。现在给我们一个区间，如果我们希望某个元素是好的，那么我们希望这个次元素没有在这个区间内，那么下面所有的元素都不会出现，这个元素就是好的。

预处理出来每个元素的次元素下标后，问题转化为区间求有多少个数小于给定数，经典离线树状数组问题。

AC代码：http://oj.daimayuan.top/submission/301595

---

#709. 最大权值划分

题意：对于一段序列，定义这段序列的权值为这段序列的极差，即序列的最大值与最小值之差。给定一个序列 $a$ ，你可以将它划分成任意段连续的序列，求出每一段的权值和的最大值。$(n\le 10^6)$

题解：(DP)代码源每日一题 Div1 最大权值划分

思路：首先容易想到把序列贪心分块为 LIS 和 LDS 计算，然而很容易 wa。我们可以 DP，定义 $dp(i)$ 表示前 $i$ 个数的最大值，然而发现转移是和上个数位于 LIS 或 LDS 有关的，因此再开一维用来区分。定义 $dp(i,j)$ 表示前 $i$ 个数的最大值，且当 $j=0/1$ 表示 $a_i$ 位于下降 / 上升序列。

AC代码：http://oj.daimayuan.top/submission/302950