单调队列优化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),即

\[f_{i,j} = - {ap}_i \times j (0 \le j \le {as}_i) \]

  • 不买也不卖:无变化,即

\[f_{i, j} = f_{i - 1, j} \]

  • 买入:交易间隔天数为 \(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;
}