设$f[i,j]$表示 第i个粉刷匠 刷到第j个墙的最大花费

f[i,j] = max(f[i,j-1], f[i-1,j]);

f[i,j] = max{f[i-1, k] + (j-k)*p[i].p} (p[i].s - p[i].l<= k < p[i].s) 

那么我们发现，那个取max的似乎可以用单调队列搞？

max{f[i-1, k] - k*p[i].p} + j * p[i].p

然后就可以愉快地单调队列啦

# include <stdio.h>
# include <algorithm>
# include <queue>
using namespace std;

int n, k;
struct fence {
	int l, p, s;
	bool operator < (const fence& a) const {
		return s < a.s;
	}
}p[120];

struct pqd {
	int v, pos;
	pqd() {}
	pqd(int _v, int _pos) : v(_v), pos(_pos) {}
	bool operator < (const pqd &a) const {
		return v < a.v || (v == a.v && pos > a.pos);
	}
};

priority_queue<pqd> q;

int f[120][16010];
// f[i,j] 表示 第i个人，刷到j墙的最大值
// f[i,j] = max(f[i,j-1], f[i-1,j]);
// f[i,j] = max{f[i-1, k] + (j-k)*p[i].p} (p[i].s - p[i].l<= k < p[i].s) 
// max{f[i-1, k] - k*p[i].p} + j * p[i].p;

int main() {
	scanf("%d%d", &n, &k);
	for (int i=1; i<=k; ++i) scanf("%d%d%d", &p[i].l, &p[i].p, &p[i].s);
	sort(p+1, p+k+1);
	for (int i=1; i<=k; ++i) {
		while(!q.empty()) q.pop();
		for (int j=max(0, p[i].s-p[i].l); j<p[i].s; ++j) {
			pqd t(f[i-1][j] - j * p[i].p, j);
			q.push(t);
		}
		for (int j=1; j<=n; ++j) {
			f[i][j] = max(f[i-1][j], f[i][j-1]);
			if(j < p[i].s || j >= p[i].s + p[i].l) continue;
			while(!q.empty() && q.top().pos < j - p[i].l) q.pop();
			if(q.empty()) continue;
			f[i][j] = max(f[i][j], q.top().v + j*p[i].p);
		}
	}
	printf("%d\n", f[k][n]);
	return 0; 
}