有时候双指针会很简单
题解 #
不难看出所有打开的图片是所有图片的一个子段。我们可以枚举所有左端点然后用双指针找到最右的端点。
Code #
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename... T> void rd(T&... args) {((cin>>args), ...);}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,a,b,T;
string s;
rd( n,a,b,T,s);
int ans=0;
vector<ll> t(2*n);
forn(i,n){
t[i]=t[i+n]=(s[i]=='w'?b+1:1);
}
for(int i=1;i<2*n;i++) t[i]+=t[i-1];
int r=n;
auto f=[&](int l,int r){
ll res=t[r]-t[l-1];
ll di=r-l+min(r-n,n-l);
return res+di*a;
};
for(int l=1;l<=n;l++){
while(r+1<l+n&&f(l,r+1)<=T) r++;
if(f(l,r)<=T) ans=max(ans,r-l+1);
}
cout<<ans;
return 0;
}