自动搬运

查看原文

来自洛谷，原作者为

	zhuoheng ENFP-T 是你的卓卓捏，但也是某人的，唉

搬运于2025-08-24 23:11:20，当前版本为作者最后更新于2025-03-23 10:49:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

简化一下题意：
给定一个长为 $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;
}