2023牛客暑假多校5

G

签到题。

双指针即可。

代码

#include<bits/stdc++.h>
#define N 1000010

using namespace std;

int n,k,a[N],s[N][5];

int sum(int l,int r,int x) {
    return s[r][x]-s[l-1][x];
}
void work() {
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) s[i][a[i]]=1;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=4;j++) s[i][j]+=s[i-1][j];
    }
    int r=1,ans=n;
    for(int l=1;l<=n;l++) {
        while(sum(l,r,1)<1&&r<=n) r++;
        while(sum(l,r,2)<1&&r<=n) r++;
        while(sum(l,r,3)<1&&r<=n) r++;
        while(sum(l,r,4)<k&&r<=n) r++;
        if(r>n) break;
        ans=min(ans,r-l+1);
    }
    cout<<ans<<endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    work();
    return 0;
}

---

H

首先若 $m>n$ ，由于 $sz$ 递增，所以只需用后 $n$ 个取即可。

定义 $g[l][r][k]$ 表示区间 $[l,r]$ 用容量为 $k$ 的包取的最大价值，可以用区间 DP 求得，相当于一个每次加一个物品的背包。

定义 $dp[i][j]$ 表示目前是第 $i$ 个操作，处理到了第 $j$ 个奶酪。容易推得递推式，答案取 max 即可。

代码

#include<bits/stdc++.h>
#define N 100010
#define M 210

using namespace std;

int n,m,a[M],b[M],sz[N],g[M][M][M],dp[M][M],ans=0;

void work() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    int maxn=0;
    for(int i=1;i<=m;i++) {
        cin>>sz[i];
        maxn=max(maxn,sz[i]);
    }
    for(int len=1;len<=n;len++) {
        for(int l=1;l+len-1<=n;l++) {
            int r=l+len-1;
            for(int k=maxn;k>=a[r];k--) g[l][r][k]=max(g[l][r-1][k],g[l][r-1][k-a[r]]+b[r]); 
            for(int k=a[r]-1;k>=0;k--) g[l][r][k]=g[l][r-1][k];
        }
    }   
    if(m<=n) {
        for(int i=1;i<=m;i++) {
            for(int j=1;j<=n;j++) {
                dp[i][j]=dp[i-1][j];
                for(int k=0;k<j;k++) {
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+g[k+1][j][sz[i]]);
                }
                ans=max(ans,dp[i][j]);
            }
        }
    }
    else {
        int A=m-n;
        for(int i=m-n+1;i<=m;i++) {
            for(int j=1;j<=n;j++) {
                dp[i-A][j]=dp[i-A-1][j];
                for(int k=0;k<j;k++) {
                    dp[i-A][j]=max(dp[i-A][j],dp[i-A-1][k]+g[k+1][j][sz[i]]);
                }
                ans=max(ans,dp[i-A][j]);
            }
        }
    }
    cout<<ans<<endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    work();
    return 0;
}