7.6 做题笔记

笔记、梳理、题解合三为一的产物。

P2569 [SCOI2010] 股票交易

考虑 DP，数据允许开到平方级别。

设 \(f_{i,j}\) 表示第 \(i\) 天持有 \(j\) 张股票的最大钱。

四种转移：

1. 凭空买入，即本次买入与前面无关。\(f_{i,j}=-ap_i\cdot j\)。

2. 不买不卖，直接从前些天转移。$f_{i,j}=\max{f_{i,j},f_{i-1,j}} $。

3. 在前面交易（买或卖）基础上买入，需要满足“两次交易间隔 \(w\) 天”的条件。

   虽然不一定上一次交易就是第 \(i-w-1\) 天，但是由转移 2 得，\(f_{i-w-1,k}\) 已经是前面这些天的最优答案，所以可以从这天转移到今天。

   注意买入的数量不要超过 \(as_i\)。方程为：\(f_{i,j}=\max\{f_{i,j},f_{i-w-1,k}-(j-k)\cdot ap_i\}\; (j-as_i\leq k<j)\)。

4. 与转移 3 类似，在前基础上卖出。方程为：\(f_{i,j}=\max\{f_{i,j},f_{i-w-1,k}+(k-j)\cdot bp_i\}\; (j<k\leq j+bs_i)\)。

发现转移 3，4 均为立方级别时间复杂度。\(\max\) 转移可以考虑单调队列优化。

根据乘法分配律，转移 3 方程实际为：\(f_{i,j}=\max\{f_{i,j},f_{i-w-1,k}+k\cdot ap_i\}-j\cdot ap_i\)。转移 4 类似，就不写了。区间取最大值的操作，单调队列可完成。

转移时注意顺序与逆序，不要把已更新过的拿来更新其他状态。

「一本通 5.5 例 2」最大连续和

时间只允许线性级别。设 \(f_i\) 为以 \(i\) 结尾的长度不超过 \(m\) 的子串的最大和。

朴素转移：\(f_i=\max_j\{\sum\limits_{k=j}^i a_k\}\;(j>i-m)\)。

预处理前缀和，则 \(f_i=\max_j\{sum_i-sum_{j-1}\}\;(j>i-m)\)。

把 \(sum_i\) 提出来，再把 \(-sum_{j-1}\) 去负号，\(\max\) 也就变成了 \(\min\)：\(f_i=sum_i-\min_j\{sum_{j-1}\}\)。

可以用单调队列解决这个 \(\min\)。

P3089 [USACO13NOV] Pogo-Cow

时间允许平方级别。设 \(f_{i,j}\) 表示当前在 \(i\) 点，从 \(j\) 点跳来的最大得分。首先按坐标顺序排序。

立方转移：\(f_{i,j}=\max\{f_{j,k}\}+p_i\;(x_j-x_k\leq x_i-x_j)\)。

这里有一个建立 DP 方程式的 trick：尝试一下把 \(f_{i-1,j}\) 带入 \(f_{i,j}\)。\(f_{i,j}=f_{i-1,j}-p_{i-1}+p_i\)。

注意这里 \(f_{i-1,j}\) 的范围是 \(x_{j}-x_k\leq x_{i-1}-x_j\)，但是由于 \(x_i>x_{i-1}\)，所以满足 \(f_{i,j}\) 范围的 \(k\) 会比满足 \(f_{i-1,j}\) 范围的 \(k\) 要多。这里简单用 while 拓展一下就好了。

题意是可以一直向左或一直向右，正反做两次 DP 即可。

P2627 [USACO11OPEN] Mowing the Lawn G

只允许线性复杂度。设 \(f_{i,0/1}\) 表示前 \(i\) 头奶牛中 不选/选 这头奶牛。\(f_{i,0}=\max\{f_{i-1,0},f_{i-1,1}\}\)，\(f_{i,1}=\max_j\{f_{j,0}+\sum\limits_{k=j+1}^iE_k\}\;(i-K\leq j< i)\)。

预处理前缀和，\(f_{i,1}=\max\{f_{j,0}+sum_i-sum_{j}\}=\max\{f_{j,0}-sum_j\}+sum_i\)。单调队列维护 \(\max\)。