这道单调队列优化DP非常好。阅读完题后我们首先可以知道,要让这个序列有序,我们需要先按照升序对木匠必须粉刷的板子进行排序。
这样之后我们可以设置出一个很显然的状态f[i][j]表示:前i个木匠,处理完了前j块木板的最大值(处理不一定都刷)
在处理的时候我们应用最典型的线性DP模板,从0 - j 中选出一个k进行从上一个状态,即f[i-1][k]转移过来,此时的状态转移方程为
f[i][j] = max{f[i-1][k] + p[i] * (j - k),f[i-1][j], f[i][j-1]}//对应这个木匠不刷,和这个木匠不刷j,只刷到j-1
复杂度为O(N^2 * M)
我们发现在这个式子中 J 是不断单调像右的,而 K 出于 S[i] 单调递增, k >= s[i] - l[i] ,所以也是单调递增的,故可以维护单调队列。
值得注意的是单调队列维护的是上一个状态的范围的值,所以理应可以想到 K (或者说是J) 一定要 < S[i] 可以在代码里仔细体会
所以上个状态单调队列的范围就是 s[i] - 1, s[i] - 1 - l[i], 当前状态的取值范围为 s[i] 到 s[i] + l[i]
代码很有意思,多多琢磨
代码:
#include <bits/stdc++.h> using namespace std; int n, m, ans; int f[105][16005]; struct node{ int l; int p; int s; }a[105]; int q[16005]; bool cmp(node i,node j){ return i.s < j.s; } int main(){ scanf("%d %d", &n, &m); for(int i = 1;i <= m;++ i){ scanf("%d %d %d", &a[i].l, &a[i].p, &a[i].s); } sort(a + 1,a + m + 1, cmp); for(int i = 1;i <= m;++ i){ int h = 0,t = -1; for(int j = 0;j <= n;++ j){ f[i][j] = f[i-1][j]; if(j) f[i][j] = max(f[i-1][j], f[i][j-1]); if(h <= t && q[h] < j - a[i].l) h ++; if(j < a[i].s){//可以考虑入队了,队列只寸编号 while(h <= t && f[i-1][q[t]] + a[i].p * (j - q[t]) <= f[i-1][j] + (j - j) * a[i].p) t --; q[++ t] = j; } if(j >= a[i].s && h <= t && j <= a[i].s + a[i].l){ f[i][j] = max(f[i][j], f[i-1][q[h]] + (j - q[h]) * a[i].p); } } } cout << f[m][n]; return 0; }