标签(空格分隔): dp 单调队列优化
题目描述
有 N 块木板从左到右排成一行, 有 M 个工匠对这些木板进行粉刷, 每块木板至多被粉刷一次.
第 i 个木匠要么不粉刷, 要么粉刷包含木板 \(S_i\) 的, 长度不超过 $ L_i $ 的连续的一段木板, 每粉刷一块可以得到 $ P_i $ 的报酬.
不同工匠的 \(S_i\)不同.
请问如何安排能使工匠们获得的总报酬最多.
输入格式
第一行包含两个整数 N 和 M.
接下来 M 行, 每行包含三个整数 Li,Pi,Si.
输出格式
输出一个整数, 表示结果.
数据范围
1≤N≤16000,
1≤M≤100,
1≤Pi≤10000
输入样例:
- 8 4
- 3 2 2
- 3 2 3
- 3 3 5
- 1 1 7
输出样例:
17
显然, 这是一道单调队列优化的模板题.
首先, 我们考虑这个单调队列.
什么是单调队列 ?
单调队列, 指的是一个保存当前状态的决策点集合的队列. 队列的队首即是当前的最优决策. 但在状态转移的过程中, 需要不断维护. 时间复杂度为 O(阶段数 * 状态数)
维护单调队列有两种方式.
检查队首的合法性
在队尾删除无用决策
提一嘴, 这里的单调是 k 单调递增, calc(i,k)单调递减
首先, 这一题有三个原始状态状态:
第 i 个 painter 什么也不刷, 即 f[i - 1,j]
第 j 块板子不刷, 即 f[i, j - 1]
第 i 个工匠粉刷 k + 1 到 j 块板子 .
由题面得: 该工匠粉刷不超过 Li 块, 且必须刷 Si, 所以需要满足 :
\[ k + 1 <= S_i <= i \qquad and \qquad j - k <= L_i \]
所以有状态转移方程 :
\[ f[i, j] = \max_{ j - L_i \leqslant k \leqslant S_i - 1} \{ f[i - 1, k] + P_i * (j - k) \} \] 显然, 在决策的过程中 \(P_i * j\) 是一个 "等效" 的常量, 所以将原转移方程改写为 :
\[ f[i, j] = P_i * j + \max_{ j - L_i \leqslant k \leqslant S_i - 1} \{ f[i - 1, k] - P_i * k \} \]
其中, 我们就可以把 \(f[i - 1, k] - P_i * k\) 写成下文的 calc 函数
剩下的和着代码一起讲.
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn = 16000 + 5;
- const int maxm = 100 + 5;
- int n, m;
- int Queue[maxn];// 单调队列本体
- struct node {
- int l, p, s;
- }painter[maxm];
- // 代表每个粉刷匠的 l,p,s
- int f[maxm][maxn];
- //f[i][j] : 代表考虑第 i 位粉刷匠刷到第 j 块板子 (中间可以有不刷的) 能 get 的最大报酬
- int calc(int i, int k){
- return f[i - 1][k] - painter[i].p * k;
- }
- bool cmp(node a, node b){
- return a.s <b.s;
- }
- int main(){
- scanf("%d%d", &n, &m);
- for(int i = 1;i <= m;i ++){
- scanf("%d%d%d", &painter[i].l, &painter[i].p, &painter[i].s);
- }
- sort(painter + 1, painter + 1 + m, cmp);
- // 排序, 使得每个粉刷匠刷的木板都在前一个之后, 我们就可以按顺序进行 dp
- for(int i = 1;i <= m;i ++){
- int h = 1, t = 0;//head & tail
- for(int k = max(0, painter[i].s - painter[i].l);k <= painter[i].s - 1;k ++){
- while(h <= t && calc(i, Queue[t]) <= calc(i, k))t --;
- // 当新决策比你小又比你强, 那你就打不过他了 QAQ. 人话: 当新决策点的报酬比当前队尾的大, 又因为在 j 不断增加的过程中当前队尾的决策点一定比新决策点更早从 [j - Li, Si - 1] 退出, 因此新决策点的 "生存能力" 较强, 则队尾一定为无用决策, delete 掉, 最后加入新的决策点
- Queue[++ t] = k;
- }// 这几行是用来计算初始决策的. 把从 max(Si - Li, 0) ~ s[i] - 1 的优秀的决策点取出, 检查, 入队
- for(int j = 1;j <= n;j ++){
- f[i][j] = max(f[i - 1][j], f[i][j - 1]);
- // 不刷时的转移
- if(j>= painter[i].s){
- while(h <= t && Queue[h] < j - painter[i].l){
- // 当队首不在 [j - Li, Si - 1] 之中时, 无法刷到 Si, 所以该退役了.
- h ++;
- }
- if(h <= t){
- f[i][j] = max(f[i][j], calc(i, Queue[h]) + painter[i].p * j);
- // 若队中还有决策点, 则最优的决策点就为队首.
- }
- }
- }
- }
- cout << f[m][n];
- // 输出了
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3157251.html