一道单调队列优化(DP)。
原题链接
设(f[i][j])表示前(i)个工匠粉刷前(j)块木板(可以有不刷的木板)能获得的最大报酬。
- 第(i)个工匠可以不刷第(j)块木板,此时(f[i][j]=f[i-1][j])。
- 第(j)块木板可以不刷,此时(f[i][j]=f[i][j-1])。
- 第(i)个工匠刷第(k+1sim j)块木板,(k+1leqslant S_ileqslant j,j-kleqslant L_i),此时(f[i][j]=maxlimits_{j-L_ileqslant kleqslant S_i-1}{f[i-1][k]+P_i imes (j-k)}, ext{且}jgeqslant S_i)
考虑化简第三个转移方程
(f[i][j]=maxlimits_{j-L_ileqslant kleqslant S_i-1}{f[i-1][k]+P_i imes (j-k)})
( \,=maxlimits_{j-L_ileqslant kleqslant S_i-1}{f[i-1][k]+P_i imes j-P_i imes k})
( \,=P_i imes j+maxlimits_{j-L_ileqslant kleqslant S_i-1}{f[i-1][k]-P_i imes k})
这样我们就可以用单调队列维护这个(max),将复杂度降至(O(1))。
总时间复杂度(O(nm))。
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 16010;
const int M = 110;
struct dd {
int L, P, S;
};
dd a[M];
int f[M][N],q[N];
int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c<'0' || c>'9'; c = getchar())
p = (c == '-' || p) ? 1 : 0;
for (; c >= '0'&&c <= '9'; c = getchar())
x = x * 10 + (c - '0');
return p ? -x : x;
}
inline int maxn(int x, int y)
{
return x > y ? x : y;
}
int comp(dd x, dd y)
{
return x.S < y.S;
}
int calc(int i, int k)
{
return f[i - 1][k] - a[i].P*k;
}
int main()
{
int i, j, n, m, k, l, r;
n = re();
m = re();
for (i = 1; i <= m; i++)
{
a[i].L = re();
a[i].P = re();
a[i].S = re();
}
sort(a + 1, a + m + 1, comp);
for (i = 1; i <= m; i++)
{
for (l = 1, r = 0, k = maxn(0, a[i].S - a[i].L); k <= a[i].S - 1; k++)
{
while (l <= r && calc(i, q[r]) <= calc(i, k))
r--;
q[++r] = k;
}
for (j = 1; j <= n; j++)
{
f[i][j] = maxn(f[i - 1][j], f[i][j - 1]);
if (j >= a[i].S)
{
while (l <= r && q[l] < j - a[i].L)
l++;
if (l <= r)
f[i][j] = maxn(f[i][j], calc(i, q[l]) + a[i].P*j);
}
}
}
printf("%d", f[m][n]);
return 0;
}