一本通题解
T2：
再也不想碰这道题了。。。写了一下午。
我们先设状态 \(dp[i][j]\) 表示前i个刷匠，考虑了前 \(j\) 个木板后所获得的最大价值(\(j\) 个木板可以有空余)。
然后枚举前 \(i\) 个刷匠，枚举每一条木板。
对于一条木板可以此刷匠根本不刷，或不刷当前木板，状转方程：
\[dp[i][j]=max(dp[i-1][j],dp[i][j-1]) \]还可以刷以这一块木板为结尾的连续一段区间，这个转移条件为 \(j>=s[i]\) 和 \(j-l[i]+1<=s[i]\)，我们把这一段要刷的区间设为 \([k+1,j]\) 状转方程
\[dp[i][j]=\max^{k<s[i]}_{k=j-l[i]} \{dp[i-1][k]+p[i]*(j-k)\} \]\(p[i]*j\) 是固定的我们可以把它提出来
\[dp[i][j]=p[i]*j+\max^{k<s[i]}_{k=j-l[i]} \{dp[i-1][k]-p[i]*k\} \]后面这一堆我们可以用单调队列维护，注意到因为单调队列右端点是固定的 \(s[i]\)，所以我们可以先预处理出单调队列然后维护单调队列的头即可。
注意一些边界条件特判。
T3：
比较巧妙的优化，因为注意到我们是从i的前k个dp数组中转化dp[i]的，所以单调队列来维护前k位dp最小值，但是，你会发现如果前面的高度小于此树高，就会带来1的贡献，但是它只有1啊，所以我们只需要让高度小的在单调队列前即可
注意：树高是严格小于
T4：
时隔许久，我终于来填单调队列这一道大坑了
现在看来也没有那么难
by the way，这道题题目描述错了，输入时b，t反了，原题为CF372C
首先我们枚举烟花，从时间从大到小的顺序，然后再枚举在哪个位置转移的话，就是从 \(t_i~t_{i-1}\) 这段时间能到这个位置的所有位置都可以转移到这，然后这个转移可以用单调队列优化
T5：
首先注意题目中的几个小细节：要先从0号节点出发，也就是我们需要手动添加一个距离为0，权值为0的节点，其次是可以在任意位置结束，就是只要存在dp值大于k就可以了
很明显这题一眼二分，然后我们根据二分出的g来确定单调队列的范围，然后转移即可
注：细节若一个点无法从原先的点转移过来，就把这个点的dp设为-inf
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5,inf=1e18;
int n,d,k,mx,q1,q2;
int u[N],w[N],q[N],dp[N];
void add(int x,int z){
while(q1<=q2&&u[q[q1]]<z) q1++;
while(q1<=q2&&dp[q[q2]]<=dp[x]) q2--;
if(u[x]<z) return;
q[++q2]=x;
}
bool check(int g){
for(int i=0;i<=n;i++) dp[i]=0,q[i]=0;
dp[0]=0;
u[0]=0;
q1=1,q2=0;
int l=max(d-g,1ll),r=d+g;
for(int i=1,j=0;i<=n;i++){
while(u[j]<=u[i]-l){
add(j,u[i]-r);
j++;
}
while(q1<=q2&&u[q[q1]]<u[i]-r) q1++;
if(q1>q2){
dp[i]=-inf;
continue;
}
dp[i]=dp[q[q1]]+w[i];
if(dp[i]>=k) return 1;
}
return 0;
}
signed main(){
scanf("%lld%lld%lld",&n,&d,&k);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&u[i],&w[i]);
mx=max(u[i],mx);
}
int l=0,r=mx;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%lld",l);
}
T6：
本质上是单调栈，我们维护一个递增的单调栈，然后假如i元素被j元素弹出，说明i元素的一个边界为j元素，所以正反跑一遍单调栈，统计左右边界
T7：
板子题，然后记录一下从哪里转移过来的就好了
T8：
二分单调队列长度，板子
T9：
我们设 \(dp[i]\) 为 \((1,i)\) 不包含违禁词的最小减少量，然后我们设 \(f[i]\) 为以 \(i\) 结尾，不包含违禁词的区间的开头，注意：只有满足有单词以 \(i\) 结尾，才进行转移，所以转移就是 \(dp[i]=\max ^i_{k=f[i]}\{ dp[i-1]+a[i] \}\)
然后我们对每一个单词跑一遍kmp，然后预处理出 \(f[i]\) ，只有有值才进行转移，转移范围就是 \(f[i]\)，用单调队列维护即可
T10：
毒瘤题，题解不可看
朴素dp： \(f_i=\min\{f_j+\max_{k=j+1}^i a_k\}\)，\(j\) 满足 \(\sum^i_{j=x} a_x<m\)
我们先预处理对于每一个 \(i\) 的 \(j\) 的范围为 \(f_i\)，然后对于这个范围我们可以维护一个单调递减的队列，这样就去掉了内层的 \(\max\) 限制，考虑如何拆掉第二层限制，我们观察 \(f_i\) 的性质，发现它是单调递增的，我们考虑我们的
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=1e5+5;
int n,m,q1,q2;
int a[N],sum[N],f[N],q[N],num[N],dp[N];
priority_queue<pii,vector<pii>,greater<pii> >mn,del;
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
if(a[i]>m){
printf("-1");
return 0;
}
}
f[0]=1;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i];
f[i]=f[i-1];
while(sum[i]>m){
sum[i]-=a[f[i]];
f[i]++;
}
// printf("%d ",f[i]);
}
// printf("\n");
q1=1,q2=0;
for(int i=1;i<=n;i++){
while(q1<=q2&&q[q1]<f[i]){
del.push({num[q[q1]],q[q1]});
q1++;
}
while(q1<=q2&&a[q[q2]]<=a[i]){
del.push({num[q[q2]],q[q2]});
q2--;
}
q[++q2]=i;
if(q1==q2) num[i]=dp[f[i]-1]+a[i];
else num[i]=dp[q[q2-1]]+a[i];
mn.push({num[i],i});
del.push({num[q[q1]],q[q1]});
num[q[q1]]=dp[f[i]-1]+a[q[q1]];
mn.push({num[q[q1]],q[q1]});
while(!del.empty()){
if(del.top()!=mn.top()) break;
del.pop(),mn.pop();
}
if(i!=1) dp[i]=mn.top().first;
else dp[i]=a[i];
// printf("%d %d %d\n",dp[i],num[i],mn.top().second);
// for(int j=q1;j<=q2;j++){
// printf("%d ",q[j]);
// }
// printf("\n");
}
printf("%lld",dp[n]);
return 0;
}