Fence
题面
有 N 块木板从左到右排成一行，有 M 个工匠对这些木板进行粉刷，每块木板至多被粉刷一次。
第 i 个木匠要么不粉刷，要么粉刷包含木板 \(S_i\) 的，长度不超过 \(L_i\) 的连续的一段木板，每粉刷一块可以得到 \(P_i\) 的报酬。
\(1 \le N \le 16000\)
\(1 \le M \le 100\)
\(1 \le P_i \le 10000\)
题解
这道题要考虑每个工匠刷了哪个区间的木板，然后从前面一个工匠转移到下一个工匠
我们先将所有工匠按照 \(S_i\) 排序，保证无后效性，当前状态都是由已知的状态转移过来的
设 \(f(i,j)\) 表示前 \(i\) 个工匠刷前 \(j\) 个木板的最大价值
有以下转移
-
第 \(i\) 个工人不刷：\(f(i,j) = f(i - 1, j)\)
-
第 \(i\) 个工人不刷第 \(j\) 块木板：\(f(i,j) = f(i, j - 1)\)
-
第 \(i\) 个工人刷第 \(k + 1 \sim i\) 块木板： \(f(i,j) = \max_{j - L_i \le k \le S_i - 1} \{ f(i - 1, k) + (i - k) \times P_i \}\)
第三个转移的时间复杂度为 \(O(N)\) ，想想怎么优化？
第三个转移的难点在于求区间最大值，而且随着 \(j\) 变大，左边界变大，右边界不变，所以看看能不能用单调队列优化
将 \(\max\) 内的已知项移出来 \(f(i,j) = \max_{j - L_i \le k \le S_i - 1} \{ f(i - 1, k) - k \times P_i \} + i * P_i\)
发现 $\max $ 内的式子只和 \(k\) 有关，所以我们可以维护一个决策点 \(k\) 单调递增，\(f(i - 1, k) - k \times P_i\) 单调递减的队列
然后进行转移即可
code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;const int N = 1.6e4 + 10, M = 110;int n, m;
int q[N], f[M][N];
struct worker {int l, p, s;bool operator < (const worker & t) const {return s < t.s;}
} a[M];int calc (int i, int k) {return f[i - 1][k] - k * a[i].p;
}int main () {cin >> 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 + 1 + m);for (int i = 1; i <= m; i ++) {int h = 1, t = 0;for (int k = max (0, a[i].s - a[i].l); k <= a[i].s - 1; k ++) {while (h <= t && calc (i, q[t]) <= calc (i, k)) t --;q[ ++ t] = k;}for (int j = 1; j <= n; j ++) {//不刷 jf[i][j] = max (f[i - 1][j], f[i][j - 1]);if (j >= a[i].s) {while (h <= t && q[h] < j - a[i].l) h ++;if (h <= t) f[i][j] = max (f[i][j], calc (i, q[h]) + j * a[i].p);}}}cout << f[m][n] << endl;return 0;
}