#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; typedef long long LL; #define CLR(x,y) memset((x),(y),sizeof((x))) #define FOR(x,y,z) for(int (x)=(y);(x)<(z);++(x)) #define FORD(x,y,z) for(int (x)=(y);(x)>=(z);--(x)) #define FOR2(x,y,z) int (x);for((x)=(y);(x)<(z);++(x)) #define FORD2(x,y,z) int (x);for((x)=(y);(x)>=(z);--(x)) const int maxn = 5 * 1E5 + 100; char str[maxn]; int tol[maxn],n,a,b,t; int check(int x){ if(tol[x] + (x-1)*a <= t) return 1; FOR(i,1,x){ int tmp=tol[i]+(tol[n]-tol[n-(x-i)])+min((i-1)*2+(x-i),(x-i)*2+(i-1))*a; if(tmp <= t) return 1; } return 0; } int main(){ scanf("%d%d%d%d%s",&n,&a,&b,&t,str+1); FOR(i,1,n+1){ tol[i] = tol[i- 1] + 1 + (str[i] == ‘w‘?b:0); } int l = 0,r = n ,mid; while(r - l > 1){ mid = l + ((r - l + 1)>>1); if(check(mid)) l = mid; else r = mid; } printf("%d\n",check(r)?r:l); return 0; } |
[2016-03-09][codeforces][651][D][Image Preview]
原文：http://www.cnblogs.com/qhy285571052/p/5263918.html