1.
\[f[i][j]=max_{j-L[i]\leq k\leq S[i]-1}\{f[i-1][k]+P[i]*(j-k)\}\] 变形一下\[f[i][j]=P[i]*j+max_{j-L[i]\leq k\leq S[i]-1}\{f[i-1][k]+P[i]*k\}\] 当\(k_1 < k_2\)且\(f[i-1][k_1]+P[i]*k_1 \leq f[i-1][k_2]+P[i]*k_2\) 时，显然\(k_2\)比\(k_1\)更优且取到\(k_1\)时一定取得到\(k_2\)，所以可以用单调队列优化，时间复杂度\(O(NM)\)#define val(x, now, i) f[i-1][x]-P[now]*xbool cmp(int x, int y) {return S[x] < S[y];}void solve(){ n=read(), m=read(); for(int i=1; i <= m; i++) L[i]=read(), P[i]=read(), S[i]=read(), pk[i]=i; sort(pk+1, pk+1+m, cmp); for(int i=1; i <= m; i++){ l=1, r=0; int now=pk[i]; for(int j=max(S[now]-L[now], 0); j < S[now]; j++){ while(l <= r && val(q[r], now, i) <= val(j, now, i)) r--; q[++r]=j; } for(int j=1; j <= n; j++){ f[i][j]=max(f[i-1][j], f[i][j-1]); if(j >= S[now]){ while(l <= r && q[l] < j-L[now]) l++; if(l <= r) f[i][j]=max(f[i][j], val(q[l], now, i)+P[now]*j); } } } printf("%d", f[m][n]); } 2.*
3.
4.（我居然自己推出来了一个\(DP\),旋转开心）（转移方程打不出来，放弃了）
int q[Maxn], l, r;void solve(){ n=read(), mp=read(), W=read(); for(int i=1; i <= n; i++) ap[i]=read(), bp[i]=read(), as[i]=read(), bs[i]=read(); memset(f, -inf, sizeof(f)); f[0][0]=0; for(int i=1; i <= n; i++){ l=1, r=0; int pre=max(0, i-W-1); q[++r]=0; f[i][0]=f[i-1][0]; for(int j=1; j <= mp; j++){ f[i][j]=f[i-1][j]; if(j <= as[i]) f[i][j]=max(f[i][j], f[pre][0]-ap[i]*j*1ll); while(l <= r && q[l]+as[i] < j) l++; if(l <= r) f[i][j]=max(f[i][j], f[pre][q[l]]+(q[l]-j)*ap[i]); while(l <= r && f[pre][q[r]]+ap[i]*q[r] <= f[pre][j]+ap[i]*j) r--; q[++r]=j; } l=1, r=0; for(int j=mp; ~j; j--){ while(l <= r && q[l]-bs[i] > j) l++; if(l <= r) f[i][j]=max(f[i][j], f[pre][q[l]]+(q[l]-j)*bp[i]); while(l <= r && f[pre][q[r]]+bp[i]*q[r] <= f[pre][j]+bp[i]*j) r--; q[++r]=j; } } ll ans=0; for(int i=0; i <= mp; i++) ans=max(f[n][i], ans); printf("%lld", ans);} 5.
6.
（这题放普及组难了点， 二分+单调队列）\[f[i]=max_{x[i]-mx\le x[k]\le x[i]-mn}\{f[k]\}+s[i]\] 重点在于进队的时间bool check(int mid){ ll ans=0; int l=1, r=0, now=0, mx=d+mid, mn=max(1, d-mid); memset(f, -inf, sizeof(f)); f[0]=0; for(int i=1; i <= n; i++){ while(x[i]-x[now] >= mn) {while(l <= r && f[q[r]] <= f[now]) r--; q[++r]=now++;} while(l <= r && x[q[l]]+mx < x[i]) l++; if(l <= r) f[i]=max(f[q[l]]+val[i], f[i]); if(f[i] >= k) return 1; } return 0; } 7.[[NOI2005]瑰丽华尔兹] ()
\[dp[i][x][y]=max_{|tx-x|+|ty-y| \le T}\{dp[i-1][tx][ty]+|tx-x|+|ty-y|\}\] 分四种情况后就非常好讨论单调性了（绝对值全去掉了）int q[Maxn], pos[Maxn], l, r;void push(int now, int pre){ if(pre == -inf) return ; while(pre-now >= q[r] && l <= r) r--; q[++r]=pre-now; pos[r]=now;}void cal(int kd, int x, int y, int d, int T){ l=1, r=0; int now=1; while(x <= n && y <= m && x >= 1 && y >= 1){ if(map[x][y] == 'x') l=1, r=0; else push(now, f[kd-1][x][y]); while(l <= r && now-pos[l] > T) l++; if(l <= r) f[kd][x][y]=q[l]+now; else f[kd][x][y]=-inf; ans=max(ans, f[kd][x][y]); x+=nx[d], y+=ny[d]; now++; }}