题目描述
有N块木板从左到右排成一行,有M个工匠对这些木板进行粉刷,每块木板至多被粉刷一次。
第 i 个木匠要么不粉刷,要么粉刷包含木板 Si 的,长度不超过 Li 的连续的一段木板,每粉刷一块可以得到 Pi 的报酬。
不同工匠的Si 不同。
请问如何安排能使工匠们获得的总报酬最多。
输入样例
8 4
3 2 2
3 2 3
3 3 5
1 1 7
输出样例
17
算法:动态规划 + 单调队列
这是一个动态规划问题。
令f[i][j]
表示前 i 个工匠粉刷前 j 块木板(可以有空着不刷的木板), 工匠们能获得的最多报酬。
状态转移方程:f[i][j]= max(1, 2, 3)
f[i-1][j]
即第 i 个工匠不刷f[i][j-1]
即第 j 块木板不刷f[i-1][k]+Pi*(j-k)
其中 j-Li ≤k ≤Si-1 && j ≥ Si 即第i个工匠刷第 k+1 到第 j 块木板
事实上,对于第3种转移方式可以改写成f[i][j] = Pi*j + max(f[i-1][k]-Pi*k)
当 j 增大时,对于k1与k2(k1<k2<Si - 1)来说,显然k1会更早离开 [j - Li, Si - 1]这个区间,
与此同时,如果f[i-1][k1]-Pi*k1 ≤ f[i-1][k2] - Pi*k2
,那么k2显然比k1更优,即k1是无用的决策,应排除出候选集合。
所以我们可以维护一个 k 单调递增,f[i-1][k] - Pi*k
单调递减的队列,该队列维护方式如下:
- 当j变大时,从队头将小于 j - Li 的决策出队
- 新的决策入队时,在队尾将破坏
f[i-1][k] - Pi*k
的单调性的决策出队,然后将新的决策入队
那么对于每种情况,最优决策即为队头。
需要注意的是,如果Si - Li小于0,那么k应该从0开始。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 16010, M = 110;
typedef struct Carpenter {
int l, p, s;
bool operator< (const Carpenter& t) const {
return s < t.s;
}
} Carpenter;
int q[N], f[M][N];
Carpenter carpenters[M];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) scanf("%d%d%d", &carpenters[i].l, &carpenters[i].p, &carpenters[i].s);
sort(carpenters + 1, carpenters + m + 1);
for (int i = 1; i <= m; ++i) {
int front = 0, rear = -1;
for (int j = 0; j <= n; ++j) {
f[i][j] = f[i - 1][j];
if (j) f[i][j] = max(f[i][j], f[i][j - 1]);
int l = carpenters[i].l, p = carpenters[i].p, s = carpenters[i].s;
if (front <= rear && q[front] < j - l) front ++;
if (front <= rear && j >= s) {
int k = q[front];
f[i][j] = max(f[i][j], f[i - 1][k] + (j - k) * p);
}
if (j < s) {
while (front <= rear && f[i - 1][q[rear]] - q[rear] * p <= f[i - 1][j] - j * p) rear --;
q[ ++rear ] = j;
}
}
}
printf("%d\n", f[m][n]);
return 0;
}