专栏文章

P9180 || [COCI 2022/2023 #5] Slastičarnica

kkanlla
P9180题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mip8wd8e
此快照首次捕获于
2025/12/03 08:04
3 个月前
此快照最后确认于
2025/12/03 08:04
3 个月前
查看原文

思路

暴力

首先 qq 的范围不重要，因为你最多只能进行 nn 次操作。尝试一番后发现不太可以贪心，考虑 dp。
数据范围启示着三维，那就可以用类似于区间 dp 的方式去进行，想到这点就很容易地给出 fi,l,rf_{i,l,r}，表示第 ii 次询问，处理完后剩区间 [l,r][l,r] 是否可行。
具体地，可以从左转移的条件：
min⁡l−d≤j≤l−1Aj≥s 且 ∃k∈[1,1−d],fi,k,l=1\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
同理，可以从右转移的条件：

正解

其实暴力打出来了的话这个就很显然了吧？
发现 fi,l,rf_{i,l,r} 的可行性 dp 很冗余，考虑能不能观察出一些性质让它减掉一维。容易发现，当 i,li,l 确定时，rr 的可行是有单调性的，即我们可以找到一个临界 xx，使其满足以下条件：
∀j∈[1,x],fi,l,j=1 且 ∀k∈[x+1,n],fi,l,k=0\forall j \in[1,x],f_{i,l,j}=1 \ \text{且} \ \forall k \in[x+1,n],f_{i,l,k}=0
重新定义 fi,lf_{i,l} 表示第 ii 次询问，处理完后可行且以 ll 为左端点的区间的最远右端点。下面我们分别考虑从左转移和从右转移的情况。
从左转移的条件很显然，为 min⁡l−d≤j≤l−1Aj≥s\min\limits_{l-d\le j\le l-1}{A_j }\ge s 这个拿 st 表随便维护一下就好了。转移公式为 fi,l=max⁡(fi,l,max⁡1≤j≤l−dfi−1,j)f_{i,l}=\max(f_{i,l},\max\limits_{1\le j\le l-d}f_{i-1,j})，可以拿前缀和维护。
从右转移稍微复杂一点。当且仅当 rr 满足min⁡r+1≤j≤r+dAj≥s\min\limits_{r+1\le j\le r+d}{A_j}\ge s 时可以进行转移。定义数组 RxR_x 表示 xx 及之前能满足该要求的最大值为多少，这样我们就可以先预处理，再在进行转移时快速得到可以从右转移的最大 rr 了。
这个题细节比较多，注意边界维护。

代码

注意到本文中的 ff 数组在代码中实际用的是 dpdp。
CPP
#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;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...