传送门：点击打开链接
题意：有K个工人，和长为N的篱笆，现在要给篱笆上色。每个工人坐在Si上，他能刷的最大范围是Li，且必须是一个连续子区间，而且必须过Si，他刷完后能获得Pi钱
问如何分配，使得K个工人的总利润最大
思路：先设出方程，设
dp[i][j]表示前i个工人，前j个篱笆的最大获利
那么就有
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
dp[i][j]=max(dp[i][j],dp[i-1][k]+(j-k)*P[i]); j>=S[i],k<S[i]且k+L[i]>=j
那么我们就能想到用单调队列来优化了
这里主要要想清楚k的范围，那么就好做了
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;const int MK = 1e2 + 5;
const int MX = 2e4 + 5;
const int INF = 0x3f3f3f3f;int N, K, r, c, dp[MK][MX];
struct Team {int L, P, S;bool operator<(const Team &C) const {return S < C.S;}
} A[MK];
struct Data {int id, x;Data() { }Data(int _id, int _x) {id = _id; x = _x;}
} Q[MX];int solve() {memset(dp, 0, sizeof(dp));for(int i = 1; i <= K; i++) {r = c = 0;Q[r++] = Data(0, 0);for(int j = 1; j <= N; j++) {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);if(j >= A[i].S) {while(c < r && Q[c].id + A[i].L < j) c++;if(c < r) {int Max = Q[c].x;dp[i][j] = max(dp[i][j], Max + j * A[i].P);}}if(j < A[i].S) {Data temp(j, dp[i - 1][j] - j * A[i].P);while(c < r && Q[r - 1].x < temp.x) r--;Q[r++] = temp;}}}return dp[K][N];
}int main() {//FIN;while(~scanf("%d%d", &N, &K)) {for(int i = 1; i <= K; i++) {scanf("%d%d%d", &A[i].L, &A[i].P, &A[i].S);}sort(A + 1, A + 1 + K);printf("%d\n", solve());}return 0;
}