题解 P2569 【[SCOI2010]股票交易】
Sooke
2018-01-02 20:14:52
## 思路概述
首先，不难想到本题可以用动态规划来解，这里就省略是如何想到动态规划的了。
###Q：动态规划的状态应该如何设？
###A：
观察数据范围，我们发现开一个 2000 × 2000 的数组来表示状态是没有问题的。
第一个维度，绝对用来表示是第几天，这个不用多想。
第二个维度，就需要稍微思考思考，我们发现它应该记录拥有多少张股票。
结合一下，整理出： $f_{i,j}$ 表示第$i$天后拥有$j$张股票可以赚到的最多钱数。
###Q：动态规划的转移方程应该如何列？状态的初值怎么设？
###A：
分情况讨论。某一天，要么买股，要么卖股，要么不买也不卖。而买股又可分为两个情况，要么凭空买，跟前面交不交易没有任何关系，要么在前面交易的基础上买股，通俗一点说，也就是该状态是否需要由前面的状态转移而来。
那为什么卖股不用分为两个情况呢？仔细想想，怎么能凭空卖呢？既然和前面的贸易没有关系，也就是说手上没有任何一张股票，哪来的股票用来卖？
因此，一共有四种情况，其中只有一个情况并不需要其他状态转移，单独讨论：
**1 . 凭空买**
仅本情况下的状态可以直接赋值，其他状态初值为 -inf，即：
$f_{i,j}=-ap_i\ \times \ j$
$(0 \leqslant j \leqslant as_i)$
下面三种情况，分别可列三个状态转移方程：
**2 . 不买也不卖**
最好想也最好列转移方程的一种情况，直接由上一天转移，且拥有股票数量不变。即：
$f_{i,j}$=$max(f_{i,j}\ \,,\ \, f_{i-1,j})$
**3 . 在之前的基础上买股票**
这里的方程就比较复杂了，这里详细解释一下：
题目中指明说两次交易需要至少隔 $w$ 天。也就是说，今天是第 $i$ 天交易，那么上一次交易最近是在第 $i - w - 1$ 天。
可我第 $i - w - 1$ 天之前也可以交易啊？为什么偏偏是那一天，而不是第 $i - w - 2$ 天？
回看刚刚讨论的第 2 种情况，我们已经把某一天以前的最优答案转移到了该天，所以从那一天转移，相当于从那一天包括前面任何一天开始转移，省去了大把时间。
接下来，我们已知第 $i$ 天拥有 $j$ 张股票，假设第 $i - w - 1$ 天拥有 $k$ 张股票。
$k$ 一定比 $j$ 小，因为这一种情况是买股票，股票只能多。
但股票又不能买太多，限制最多为 $as$ 张。所以 $j - as_i$ 是底线。
继续，这次交易买了 $j - k$ 张股票，要花去 $(j - k) \times ap_i$ 元。
整理一下，转移方程为：
$f_{i,j}$=$max(f_{i,j}\ \,,\ \,f_{i-w-1,k}-(j-k)\times ap_i)$
$(j - as_i \leqslant k < j)$
**4 . 在之前的基础上卖股票**
和上面的情况特别类似，在此简单地说一下区别。
因为是卖股票，$k$ 这次要比 $j$ 大。但要小于等于 $j + bs_i$。
这次交易卖了 $k - j$ 张邮票，赚得 $(k - j) \times bp_i$ 元。
整理一下，转移方程为：
$f_{i,j}$=$max(f_{i,j}\ \,,\ \,f_{i-w-1,k}+(k-j)\times bp_i)$
$(j < k \leqslant j + bs_i)$
###Q：为什么可以使用单调性优化？
###A：
上面的 3，4 两种情况，列起来头头是道，但我们深入计算，发现时间复杂度是三次方级的。很显然，我们要想尽办法，把时间复杂度降到二次方级。
这个时候发现那两种情况，实际上可以使用单调性优化。此时达到降时间复杂度的目标。
就以第 3 种情况，在之前的基础上买股票为例子吧。
再重复提一下那个转移方程：
$f_{i,j}$=$max(f_{i,j}\ \,,\ \,f_{i-w-1,k}-(j-k)\times ap_i)$
$(j - as_i \leqslant k < j)$
运用乘法分配率：
$f_{i,j}$=$max(f_{i,j}\ \,,\ \,f_{i-w-1,k}-j\times ap_i+k\times ap_i)$
$(j - as_i \leqslant k < j)$
既然要将状态转移给 $f_{i,j}$，此时 $j$ 可以从 $max$ 中提取出，此时转移方程变为：
$f_{i,j}$=$max(f_{i,j}\ \,,\ \,f_{i-w-1,k}+k\times ap_i)-j\times ap_i$
$(j - as_i \leqslant k < j)$
此时，我们发现以上的转移方程符合单调性优化的条件，故可以使用单调性优化。
没有理解地，可以这么想：由于转移有这么一个区间前提：$(j - as_i \leqslant k < j)$，又因为转移方程中出现了 max，也就是说转移的目的是从该区间中，找到某个最大的值，基础好的你应该已经发现这就是滑动窗口了吧？只不过放进单调队列的元素，是 $f_{i-w-1,k}+k\times ap_i$，但这并不影响转移。
那么第 4 种情况的转移，我就不多解释了，它的转移方程可以整理为：
$f_{i,j}$=$max(f_{i,j}\ \,,\ \,f_{i-w-1,k}+k \times bp_i)-j \times bp_i$
$(j < k \leqslant j + bs_i)$
好像除了后面的转移区间要求，两个整理后的方程几乎都是一样的。
对了，还有一个细节，是第 3 种情况转移应该顺序，第 4 种情况转移应该逆序，这个不难理解，先自己想想吧。
## 代码实现
按照上面的思路，得到对应的代码：
```cpp
#include <cstdio>
#include <cstring>
#define Min(x , y) ((x) < (y) ? (x) : (y))
#define Max(x , y) ((x) > (y) ? (x) : (y))
int n , m , ap , bp , as , bs , w , ans = 0 , f[2001][2001] , l , r , q[2001];
// f[i][j] 表示第 i 天后拥有 j 张股票赚的最多钱数
// l , r , q[x] 用于单调队列
int main(){
scanf("%d%d%d" , &n , &m , &w);
memset(f , 128 , sizeof(f)); // 128 实际上给 f 数组赋的是 -inf，可以试试看
for(int i = 1 ; i <= n ; i++){
scanf("%d%d%d%d" , &ap , &bp , &as , &bs);
for(int j = 0 ; j <= as ; j++)
f[i][j] = -1 * j * ap; // 第 1 种情况，直接赋
for(int j = 0 ; j <= m ; j++)
f[i][j] = Max(f[i][j] , f[i - 1][j]); // 第 2 种情况，转移
if(i <= w)
continue; // 因为第 3，4 种情况都有 i - w - 1，如果 i <= w，会出现负下标
// 第 3 种情况，从小转移到大
l = 1 , r = 0; // 单调队列准备
for(int j = 0 ; j <= m ; j++){
while(l <= r && q[l] < j - as)
l++; // 把过期的元素扔掉
while(l <= r && f[i - w - 1][q[r]] + q[r] * ap <= f[i - w - 1][j] + j * ap)
r--; // 更新单调队列元素
q[++r] = j; // 插入最新元素
if(l <= r)
f[i][j] = Max(f[i][j] , f[i - w - 1][q[l]] + q[l] * ap - j * ap);
// 如果单调队列里有元素，即可转移
}
// 第 4 种情况，从大转移到小
l = 1 , r = 0; // 单调队列再次准备
for(int j = m ; j >= 0 ; j--){
while(l <= r && q[l] > j + bs)
l++; // 把过期的元素扔掉
while(l <= r && f[i - w - 1][q[r]] + q[r] * bp <= f[i - w - 1][j] + j * bp)
r--; // 更新单调队列元素
q[++r] = j; // 插入最新元素
if(l <= r)
f[i][j] = Max(f[i][j] , f[i - w - 1][q[l]] + q[l] * bp - j * bp);
// 如果单调队列里有元素，即可转移
}
}
for(int i = 0 ; i <= m ; i++)
ans = Max(ans , f[n][i]); // 最后，可以留股票（实际上不留任何股票的就是最优答案），找出最优答案
printf("%d\n" , ans);
return 0;
}
```