自动搬运

查看原文

来自洛谷，原作者为

	anll 我不会输

搬运于2025-08-24 22:46:05，当前版本为作者最后更新于2025-05-20 16:00:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

暴力

首先 $q$ 的范围不重要，因为你最多只能进行 $n$ 次操作。尝试一番后发现不太可以贪心，考虑 dp。

数据范围启示着三维，那就可以用类似于区间 dp 的方式去进行，想到这点就很容易地给出 $f_{i,l,r}$，表示第 $i$ 次询问，处理完后剩区间 $[l,r]$ 是否可行。

具体地，可以从左转移的条件：

$$\min\limits_{l-d\le j\le l-1}{A_j }\ge s \ \text{且}\ \exists k\in [1,1-d],f_{i,k,l}=1 $$

同理，可以从右转移的条件：

$$\min\limits_{r+1\le j\le r+d}{A_j}\ge s\ \text{且} \ \exists k\in [r+1,n],f_{i,l,k}=1 $$

正解

其实暴力打出来了的话这个就很显然了吧？

发现 $f_{i,l,r}$ 的可行性 dp 很冗余，考虑能不能观察出一些性质让它减掉一维。容易发现，当 $i,l$ 确定时，$r$ 的可行是有单调性的，即我们可以找到一个临界 $x$，使其满足以下条件：

$$\forall j \in[1,x],f_{i,l,j}=1 \ \text{且} \ \forall k \in[x+1,n],f_{i,l,k}=0 $$

重新定义 $f_{i,l}$ 表示第 $i$ 次询问，处理完后可行且以 $l$ 为左端点的区间的最远右端点。下面我们分别考虑从左转移和从右转移的情况。

从左转移的条件很显然，为 $\min\limits_{l-d\le j\le l-1}{A_j }\ge s$ 这个拿 st 表随便维护一下就好了。转移公式为 $f_{i,l}=\max(f_{i,l},\max\limits_{1\le j\le l-d}f_{i-1,j})$，可以拿前缀和维护。

从右转移稍微复杂一点。当且仅当 $r$ 满足$\min\limits_{r+1\le j\le r+d}{A_j}\ge s$ 时可以进行转移。定义数组 $R_x$ 表示 $x$ 及之前能满足该要求的最大值为多少，这样我们就可以先预处理，再在进行转移时快速得到可以从右转移的最大 $r$ 了。

这个题细节比较多，注意边界维护。

代码

注意到本文中的 $f$ 数组在代码中实际用的是 $dp$。

#include<cmath>
#include<iostream>
#define int long long
using namespace std;
const int N=5005;
int n,q,ans,num[N],st[N][25],dp[N][N],R[N];
void init(){
	for(int i=0;i<=n;i++) for(int j=0;j<=20;j++) st[i][j]=1e10;
	for(int i=1;i<=n;i++) st[i][0]=num[i],dp[0][i]=n;
	for(int j=1;j<=20;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
int Find(int l,int r){
	int k=log2(r-l+1);
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>q;if(q>n) q=n;
	for(int i=1;i<=n;i++) cin>>num[i];
	init();
	for(int i=1;i<=q;i++){
		int d,s,maxn=0,maxR=0;cin>>d>>s;
		for(int j=1;j<=n-d;j++){
			if(Find(j+1,j+d)>=s) R[j]=j;
			else R[j]=R[j-1];
		}
		for(int j=n-d+1;j<=n;j++) R[j]=R[j-1];
		for(int l=1;l<=n;l++){
			maxR=max(maxR,dp[i-1][l]);
			if(l-d>0) maxn=max(maxn,dp[i-1][l-d]);
			if(l-d>0&&Find(l-d,l-1)>=s&&maxn>=l)
				dp[i][l]=maxn;
			if(maxR-d>0) dp[i][l]=max(dp[i][l],R[maxR-d]);
			if(dp[i][l]<l) dp[i][l]=0;
		}
		for(int l=1;l<=n;l++) if(dp[i][l]) ans=i;
		if(ans!=i){
			for(int j=1;j<=n;j++){
				if(j+d-1>n) break;
				if(dp[i-1][j]-j+1<d) continue;
				bool st=1;
				for(int k=j;st&&k<=j+d-1;k++)
					if(num[k]<s) st=0;
				if(st){ans=i;break;}
			}
			break;
		}
	}
	cout<<ans;
	return 0;
}