题目链接:P10978 Fence - 洛谷。
本题是经典 DP 单调队列优化题型。
题目描述
一组由 $k$($1 \leq k \leq 100$) 名工人组成的团队需要粉刷一堵包含 $N$ 个木板的围栏,这些木板从左到右编号为 $1$ 到 $N$($1 \leq N \leq 16,000$)。每个工人 $i$($1 \leq i \leq k$)应该坐在木板 $S_i$ 前,他只能粉刷一个连续的区间(这意味着区间内的木板应该是连续的)。这个区间必须包含木板 $S_i$。此外,每个工人粉刷的木板数量不能超过 $L_i$ 个,并且每粉刷一个木板他会得到 $P_i$ 美元($1 \leq P_i \leq 10,000$)。每个木板最多只能由一个工人粉刷。所有的 $S_i$ 都是不同的。
作为团队的领导者,你需要为每个工人确定他们应该粉刷的区间,并且确保总收入最大化。总收入代表工人个人收入的总和。
编写一个程序来确定 $k$ 名工人获得的总最大收入。
输入格式
输入的第一行是是两个正整数 $N,k$。
接下来 $k$ 行,每行三个正整数 $L_i,P_i,S_i$。
输出格式
输出一个整数,表示总最大收入。
输入输出样例 #1
输入 #1
1 |
|
输出 #1
1 |
|
题解
状态定义和转移
定义 $f(i,j)$ 表示前 $i$ 个木匠粉刷前 $j$ 块木板获得的最大总收入。
考虑转移,共三种情况: $$ f(i,j) = \max\begin{Bmatrix} f(i-1, j) & & \ f(i, j-1) & & \ \max_{j-L_i \le k < j}\set{f(i-1, k) +p_i \times (j-k)} & k < S_i & \ \end{Bmatrix} $$
-
第 $i$ 个木匠可以什么也不刷。收入为 $f(i-1,j)$。
-
第 $j$ 个木板可以不被粉刷进行粉刷。收入为 $f(i,j-1)$。
-
第 $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)$。