1.题目相关
-
标签：
DP单调队列优化 - 题目地址：http://poj.org/problem?id=1821
- 题目大意：有 N 块连续的木板，并有 K 个工人来粉刷，但不要求全部粉刷。每个工人有三个参数：L，P，S，表示其最多粉刷连续的 L 块木板，并且每粉刷一块木板可获得 P 元，但所粉刷的木板必须包括第 S 块。输出所能获得最大价值。
2.思路
- 先以 S 为第一关键字排序，建立 DP 方程。
- dp[i][j] 表示第 i 个人粉刷到第 j 块木板，所获得最大价值。
- dp[i][j] = max{ dp[i][j-1] , dp[i-1][j] , dp[i-1][k] + (j-k)·p[i] }
- 分别表示：第 i 个人不刷、第 j 面墙不刷、第 i 个人刷 k+1 到 j 块木板。且对于第三种，需满足 j-l[i]<=k<=s[i]-1 和 s[i]<=j<=s[i]+l[i]-1。
- 建立方程后会发现，直接DP会TLE，所以要进行一些优化。
- 对于第一、第二项我们可以做到n^2，所以需要着重优化第三项。
- 整理后可以发现其可以转化为 dp[i-1][k]+k×p[i] 和 j×P[i] 这两项。
- 其中前一项可视为关于 k 的函数，后一项则是常数。并且对于每个 j 来说最优的 k 都是递增的。
- 所以就可以用一个值单调递减，位置单调递增的单调队列来维护。一开始把符合条件的 k 扫一遍，并维护队列。在递推时每次查看队头，若当前 k 对于 j 不符合，则出队，直至符合。
