P10978 Fence

题目链接：P10978 Fence - 洛谷。

本题是经典 DP 单调队列优化题型。

题目描述

一组由 $k$（$1\le k\le 100$） 名工人组成的团队需要粉刷一堵包含 $N$ 个木板的围栏，这些木板从左到右编号为 $1$ 到 $N$（$1\le N\le 16,000$）。每个工人 $i$（$1\le i\le k$）应该坐在木板 $S_i$ 前，他只能粉刷一个连续的区间（这意味着区间内的木板应该是连续的）。这个区间必须包含木板 $S_i$。此外，每个工人粉刷的木板数量不能超过 $L_i$ 个，并且每粉刷一个木板他会得到 $P_i$ 美元（$1\le P_i\le 10,000$）。每个木板最多只能由一个工人粉刷。所有的 $S_i$ 都是不同的。

作为团队的领导者，你需要为每个工人确定他们应该粉刷的区间，并且确保总收入最大化。总收入代表工人个人收入的总和。

编写一个程序来确定 $k$ 名工人获得的总最大收入。

输入格式

输入的第一行是是两个正整数 $N,k$。

接下来 $k$ 行，每行三个正整数 $L_i,P_i,S_i$。

输出格式

输出一个整数，表示总最大收入。

输入输出样例 #1

输入 #1

8 4
3 2 2
3 2 3
3 3 5
1 1 7

输出 #1

17

题解

状态定义和转移

定义 $f(i,j)$ 表示前 $i$ 个木匠粉刷前 $j$ 块木板获得的最大总收入。

考虑转移，共三种情况：

$$f(i,j)=max\left\{\begin{array}{cc}f(i-1,j)& \\ f(i,j-1)& \\ \underset{j-L_i\le k<j}{max}\{f(i-1,k)+p_i\times (j-k)\}& k<S_i& \end{array}\right\}$$

1. 第 $i$ 个木匠可以什么也不刷。收入为 $f(i-1,j)$。

2. 第 $j$ 个木板可以不被粉刷进行粉刷。收入为 $f(i,j-1)$。

3. 第 $i$ 个木匠对第 $j$ 个木板进行粉刷。枚举第 $i$ 个木匠接着从第 $k+1$ 个木板刷到 $j$（$k+L_i\ge j$），收入为 $f(i-1,k)+p_i\times (j-k)$。

状态转移时，$f(i,j)$取以上三种情况的最大值。

单调队列优化

我们发现第三种情况枚举 $k$ 的复杂度太高，需要优化。

我们把它化简为 $f(i-1,k)-p_i\times k+p_i\times j$。

我们发现，$p_i\times j$ 是固定不变的，所以只需要找出最大的，符合条件的 $f(i-1,k)-p_i\times k$。

维护一个 $k$ 单增、$f(i-1,k)-p_i\times k$ 单减的队列。只有队列中的 $k$ 可能成为最优的决策。

维护原则：如果存在 $k_1<k_2$ 且 $f(i-1,k_1)-p_i\times k_1\ge f(i-1,k_2)-p_i\times k_2$，那么 $k_1$ 应该出队。

答案即为 $f(k,n)$。