Vasya's telephone contains n photos. Photo number 1 is currently opened on the phone. It is allowed to move left and right to the adjacent photo by swiping finger over the screen. If you swipe left from the first photo, you reach photo n. Similarly, by swiping right from the last photo you reach photo 1. It takes a seconds to swipe from photo to adjacent.
For each photo it is known which orientation is intended for it — horizontal or vertical. Phone is in the vertical orientation and can't be rotated. It takes b second to change orientation of the photo.
Vasya has T seconds to watch photos. He want to watch as many photos as possible. If Vasya opens the photo for the first time, he spends 1 second to notice all details in it. If photo is in the wrong orientation, he spends b seconds on rotating it before watching it. If Vasya has already opened the photo, he just skips it (so he doesn't spend any time for watching it or for changing its orientation). It is not allowed to skip unseen photos.
Help Vasya find the maximum number of photos he is able to watch during T seconds.
The first line of the input contains 4 integers n, a, b, T (1 ≤ n ≤ 5·105, 1 ≤ a, b ≤ 1000, 1 ≤ T ≤ 109) — the number of photos, time to move from a photo to adjacent, time to change orientation of a photo and time Vasya can spend for watching photo.
Second line of the input contains a string of length n containing symbols 'w' and 'h'.
If the i-th position of a string contains 'w', then the photo i should be seen in the horizontal orientation.
If the i-th position of a string contains 'h', then the photo i should be seen in vertical orientation.
Output the only integer, the maximum number of photos Vasya is able to watch during those T seconds.
4 2 3 10
wwhw
2
5 2 4 13
hhwhh
4
5 2 4 1000
hhwhh
5
3 1 100 10
whw
0
我是先把第一个字符减去， 因为第一个肯定要读， 然后减完的t值， 如果小于0直接输出0就可以了。
然后把从前往后读的和从后往前读所花费的时间都预处理出来。 最优的情况应该是从前往后读几个， 从后往前也读几个， （几个)可以为0。 然后我们枚举从前往后读的情况， 二分查找在这种情况下， 从后往前读最多可以读多少个。 在枚举从后往前的情况， 二分从前往后的情况。
读过的照片不花费时间， 但是移动还是要花费的， 这点要注意..
#include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> #include <set> #include <string> #include <queue> #include <stack> #include <bitset> using namespace std; #define pb(x) push_back(x) #define ll long long #define mk(x, y) make_pair(x, y) #define lson l, m, rt<<1 #define mem(a) memset(a, 0, sizeof(a)) #define rson m+1, r, rt<<1|1 #define mem1(a) memset(a, -1, sizeof(a)) #define mem2(a) memset(a, 0x3f, sizeof(a)) #define rep(i, n, a) for(int i = a; i<n; i++) #define fi first #define se second typedef pair<int, int> pll; const double PI = acos(-1.0); const double eps = 1e-8; const int mod = 1e9+7; const int inf = 1061109567; const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; int pre[500005], suf[500005], b, a; int val(char c) { if(c == 'w') return b+1+a; return 1+a; } int main() { int n, t; char ch; string s, str; cin>>n>>a>>b>>t; cin>>ch; if(ch == 'w') t -= b; t--; if(t<0) { puts("0"); return 0; } int maxx = 0; cin>>s; for(int i = 0; i<=s.size(); i++) { if(i == 0) pre[i] = 0; else pre[i] = pre[i-1]+val(s[i-1]); } reverse(s.begin(), s.end()); for(int i = 0; i<=s.size(); i++) { if(i == 0) suf[i] = 0; else suf[i] = suf[i-1]+val(s[i-1]); } for(int i = 0; i<=s.size(); i++) { int l = 0, r = s.size()-i, tmp = -1; if(pre[i]>t) break; while(l<=r) { int mid = (l+r)>>1; if(pre[i]+suf[mid]+(i)*a<=t) { //i*a的意思是， 从前往后读了几个以后又移动回去的值 tmp = mid; l = mid+1; } else { r = mid-1; } } if(tmp == -1) maxx = max(maxx, i); maxx = max(maxx, i+tmp); } for(int i = 0; i<=s.size(); i++) { int l = 0, r = s.size()-i, tmp = -1; if(suf[i]>t) break; while(l<=r) { int mid = (l+r)>>1; if(pre[mid]+suf[i]+(i)*a<=t) { tmp = mid; l = mid+1; } else { r = mid-1; } } if(tmp == -1) maxx = max(maxx, i); maxx = max(maxx, i+tmp); } cout<<maxx+1<<endl; return 0; }