单调队列优化DP历险记
- 写在前面
- 简介
- 斜率优化
- 实用小技巧
- 股票交易
写在前面
记录那写抄题解水过的单调队列优化DP
简介
用到单调队列优化的情况:
- 状态转移时需要从一段固定长度的区间里找
- 区间是在不断滑动的
实现步骤:
- 检查队首是否年纪大了,是则弹出
- 检查队尾是否比要加进去的位置更优,否则弹出
- 加入新元素
- 取出队首,就是最优的位置,\(O(1)\) 转移即可
斜率优化
其实和单调队列差不多,只是队首队尾的弹出条件相对复杂,涉及斜率?
\[\frac{f(x_1) - f(x_2)}{x_1 - x_2} \]实用小技巧
- 全部赋成128其实就是极小值
memset(f, 128, sizeof f)
股票交易
Description
P2569 [SCOI2010]股票交易
Solution
状态应该是比较好想的,数据范围只有两千,涉及量有天数和股票数,所以可以设 \(f_{i, j}\) 表示到第 \(i\) 天,手里还有 \(j\) 个股票时的最大价值
分情况讨论
- 凭空买:前 \(W\) 天,没有股票,只能先买一手,所以这几天可以直接赋值,其他状态初值为 -INF,(可以用memset赋128),即
- 不买也不卖:无变化,即
- 买入:交易间隔天数为 \(W\) ,今天为第 \(i\) 天,离上次交易最近的是第 \(i - W - 1\)。
为什么一定是这一天?回看刚刚讨论的第 2 种情况,我们已经把某一天以前的最优答案转移到了该天,所以从那一天转移,相当于从那一天包括前面任何一天开始转移,省去了大把时间。
设第 \(i - W - 1\) 有 \(k\) 枚股票,因为有 \(as\) 的限制,所以 \(j - as\) 是底线,买进 \(j - k\) 张股票,要花去 \((j - k) \times {ap}i\) 转移方程为:
\[f_{i,j} = \max \{ f_{i,j}, f_{i - W - 1, k} - (k - j) \times {ap}_i \} (j - {as}_i \le k < j) \]- 卖出:交易间隔天数为 \(W\) ,今天为第 \(i\) 天,离上次交易最近的是第 \(i - W - 1\)。同上面道理差不多
因为是卖股票,\(k\) 要比 \(j\) 大,但要 $\le 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 \le j + {bs}_i ) \]但是,这样滴复杂度显然到了 \(n^3\) ,让我们考虑优化。
回到那个方程:\(f_{i,j} = \max \{ f_{i,j}, f_{i - W - 1, k} - (k - j) \times {ap}_i \} (j - {as}_i \le k < j)\)
运用乘法分配律得:$$f_{i,j} = \max { f_{i,j}, f_{i - W - 1, k} - k \times {ap}_i + j \times {ap}_i } (j - {as}_i \le k < j)$$
发现最后一项与 \(k\) 无关,\(k\) 的范围是不断移动的,符合单调队列优化的条件,维护一个区间最大值就好了
因为第四种情况调用 \(k\) 比 \(j\) 大,所以需要倒序枚举
Code
/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"<= 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);
}
}
}
int ans = -INF;
for(int i = 0; i <= MaxP; ++i){
ans = max(ans, f[T][i]);
}
printf("%d", ans);
return 0;
}