题解：P11914 [PA 2025] 上班 / Praca

· · 题解

简化一下题意：
给定一个长为 n 的字符串 s，表示 n 段时间，有三种情况，分别表示线上会议，线下会议和空闲时间。
线下会议只能在公司参加，线上会议在公司和家中均可参加，空闲时间可以做题。
可以选择使用 t 段时间通勤去到公司，但只能去一次，且通勤时间能不能做题也不能参加会议。
注意最后必须回到家中，所以必然会有两段通勤时间。
总共可以翘掉 k 次会议，只有空闲时间或者被翘掉且不在通勤的时间可以做题。

读完了题意后，这道题的大致轮廓就比较清晰了。
我们可以发现由于只能去公司一次，所以只要确定了通勤时间后做题时间可以通过前缀和直接计算。
计算过程就是把通勤时间内的会议数量 cnt 先和 k 作比较，然后大于就直接略过，小于就让 k 直接减去 cnt 然后对于通勤时间和在公司时间外的所有线下会议数量 cnt1 和剩余的 k 作比较，小于也是直接略过不考虑，然后让剩余的 k 减一次 cnt1 接着就是把剩下空闲的时间和剩余可以被翘掉的会议加到答案中。
可以发现此题数据不大，所以直接枚举通勤的时间然后比较计算最大即可。
代码如下：

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N=8001;
int n,k,t,pre1[N],pre2[N],pre3[N],mx=-1;
string s;
int gt_sm(int op,int l,int r){
    if(op==1)return pre1[r]-pre1[l-1];
    else if(op==2)return pre2[r]-pre2[l-1];
    else return pre3[r]-pre3[l-1];
}
int solve(int l,int r){
    int res,tk=k,cnt;
    tk-=gt_sm(1,l-t,l-1)+gt_sm(2,l-t,l-1);
    tk-=gt_sm(1,r+1,r+t)+gt_sm(2,r+1,r+t);
    if(tk<0)return -1;
    l-=t+1,r=min(n+1,r+t+1);
    res=gt_sm(3,1,l)+gt_sm(3,r,n);
    cnt=gt_sm(1,1,l)+gt_sm(1,r,n);
    if(tk<cnt)return -1;
    cnt+=gt_sm(2,1,l)+gt_sm(2,r,n);
    return res+min(cnt,tk);
}
int main(){
    ios;
    cin>>n>>k>>t>>s;
    for(int i=1;i<=n;++i){
        pre1[i]=pre1[i-1],pre2[i]=pre2[i-1],pre3[i]=pre3[i-1];
        if(s[i-1]=='1')pre1[i]++;
        else if(s[i-1]=='2')pre2[i]++;
        else pre3[i]++;
    }
    if(k>=pre1[n])cout<<min(n,k+pre3[n]),exit(0);
    for(int i=t+1;i<=n-t+1;++i)
        for(int j=i;j<=n-t;++j)
            mx=max(mx,solve(i,j));
    cout<<mx;
}