思路:
背包+单调队列优化dp
设$d_{i,j}$为第$i$天持有$j$股股票的最大利润.
一共有四种转移途径:
- 1 不进行交易, 转移方程为:
- 2 首次买入, 对$j \le AS_i$, 有:
- 3 再次买入, 对$i > W + 1$, 有:
- 4 卖出, 对$i > W + 1$, 有:
转移1, 2可以直接判定. 对于转移3, 4可以发现$k$的左右端点随$j$的增加单调不降, 所以可以使用单调队列优化.
对于3的转移方程, 移项可得:
同样地, 对于4的转移方程移项得:
所以使用单调队列维护的是$d_{i-W-1,k} + kAP_i$和$d_{i-W-1,k} + kBP_i$
代码:
1 |
|