AcWing 298. 围栏(单调队列优化dp)
原题链接
中等
作者:
小小_88
,
2022-09-16 20:24:50
,
所有人可见
,
阅读 329
围栏
C++ 代码
/*
本题要我们求一个粉刷方案,让报酬最大,是一个最优方案问题,可以考虑用 dp
所有木匠光这个枚举非常的乱,可以先把所有木匠按照 s[i] 排序,这样一来,每个木匠
粉刷的木板一定在上一个木匠粉刷的木板之后,使得我们能按顺序进行线性 dp
设 f[i][j] 表示安排前 i 个木匠粉刷前 j 块木板,能获得的最多报酬。
1. 第 i 个木匠可以什么也不刷,此时 f[i][j] = f[i - 1][j]
2. 第 j 块木板可以空着不刷,此时 f[i][j] = f[i][j - 1]
3. 第 i 个木匠粉刷第 k + 1 块到第 j 块木板,根据题意,该木匠粉刷总数不能超过 l[i],
且必须粉刷 s[i],所以需满足:k + 1 <= s[i] <= j && j - k <= l[i]。因此有状态转移方程:
f[i][j] = max{ f[i - 1][k] + (j - k) * p[i] } (j >= s[i], j - l[i] <= k <= s[i] - 1)
由于数据范围较大,以上算法会超时,需要进行优化,可以发现,在考虑内层循环 j 以及决策 k 时,
可把外层循环变量 i 看作定值,这样一来,状态转移方程中各项可分为两部分
1. p[i] * j,除定值 i 外,只有状态变量 j
2. f[i - 1][k] - p[i] * k,除定值 i 外,只有决策变量 k
状态方程可改写为:f[i][j] = p[i] * j + max{ f[i - 1][k] - p[i] * k } (j >= s[i], j - l[i] <= k <= s[i] - 1)
当 j 增大时,k 的取值范围上界 s[i] - 1 不变,下界 j - l[i] 变大。
我们比较一下任意两个决策 k1 和 k2,设 k1 < k2 <= s[i] - 1。因为 k2 比 k1 更靠后,所以随着 j 的增加,
k1 会比 k2 更早从范围 [j - l[i], s[i] - 1] 中被排除,如果还满足 f[i - 1][k1] - p[i] * k1 <= f[i - 1][k2] - p[i] * k2,
那么就意味着 k2 不但比 k1 更优,还比 k1 的存活时间更长,在这种情况下,k1 就是一个无用的决策,
应该被直接排除出候选决策集合。
综上所述,我们可以维护一个决策点 k 单调递增,数值 f[i - 1][k] - p[i] * k 单调递减的队列,
只有这个队列中的决策才有可能在某一时刻称为最优策略,这个单调队列支持如下操作:
1. 当 j 变大时,检查队头元素,把小于 j - l[i] 的决策出队
2. 需要查询最优策略时,队头即为所求
3. 有一个新的决策要加入候选集合时,在队尾检查 f[i - 1][k] - p[i] * k 的单调性,把无用策略从队尾直接出队,
最后把新决策加入队列
在本题中具体来说,当内层循环开始时(j = s[i]),建立一个空的单调队列,把 [max(s[i] - l[i], 0), s[i] - 1]
中的决策依次加入候选集合(执行操作 3),对于每个 j = s[i] ~ n,先在队头检查决策合法性(执行操作 1),
然后取队头为最优决策(执行操作 2)进行状态转移。
由于单调队列的优化,枚举决策的时间复杂度是线性 O(1) 的,总的时间复杂度为 O(nm)
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 16010;
struct Node
{
int l, p, s;
bool operator< (const Node &t) const //所有木匠按照 s[i] 从小到大排序
{
return s < t.s;
}
}a[N]; //记录所有木匠的信息
int n, m;
int f[N][M]; //设 f[i][j] 表示安排前 i 个木匠粉刷前 j 块木板,能获得的最多报酬
int q[M]; //单调队列
int main()
{
scanf("%d%d", &m, &n);
for(int i = 1; i <= n; i++) scanf("%d%d%d", &a[i].l, &a[i].p, &a[i].s);
sort(a + 1, a + 1 + n); //将所有木匠按照 s[i] 从小到大排序
//单调队列优化 dp
for(int i = 1; i <= n; i++)
{
int hh = 0, tt = -1; //初始化单调队列
//把最初的候选集合加入队列
for(int k = max(0, a[i].s - a[i].l); k <= a[i].s - 1; k++)
{
while(hh <= tt && f[i - 1][q[tt]] - a[i].p * q[tt] <= f[i - 1][k] - a[i].p * k) tt--; //保证加入新决策后队列的单调性
q[++tt] = k; //加入新决策
}
for(int j = 1; j <= m; j++)
{
//max{ 第 i 个木匠不粉刷, 不粉刷第 j 块木板 }
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
//粉刷第 k + 1 ~ j 块木板
if(j >= a[i].s)
{
while(hh <= tt && q[hh] < j - a[i].l) hh++; //排除队头的不合法决策
//如果队列中还有元素,就继续进行状态转移
if(hh <= tt) f[i][j] = max(f[i][j], f[i - 1][q[hh]] - a[i].p * q[hh] + a[i].p * j);
}
}
}
printf("%d\n", f[n][m]);
return 0;
}
先排序是因为贪心吧
是的,可以让木匠之间存在一个阶段性的关系,方便进行 dp