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

· · 题解

思路

暴力

首先 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

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

正解

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

发现 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;
}