将可以打针的那天编号处理出来
枚举第二针在第a[i]天打
对 a[i]-k 与 a[i]+k 进行二分,即二分第一针与第三针
我们最理想状态是a[i]-k, a[i]与a[i]+k
但二分出来的是a[l]与a[r]
因此通过偏移量abs[ (a[i]-k) - a[l] ]与abs[ (a[i]+k) - a[r] ]计算收益
两天以上才有收益 若两天正好间隔k天, 则收益为w - (k - k) * q = w,无损失
二分出来的a[l]与a[r]是第一个间隔>=目标值k的天数,因此要在a[l]与a[l - 1]之间取max
即在第一个间隔>=k与第一个间隔<k之前取max
#include <bits/stdc++.h>
#define dbg(a) cout << #a << " = " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
char s[N];
ll a[N], cnt;
ll k, w, q; // 最优天数, 收益, 损失
ll res;
ll find(int x)
{
int i = 1, j = cnt;
while(i < j)
{
int mid = i + j >> 1;
if(a[mid] < x) i = mid + 1;
else j = mid;
}
return i;
}
// 计算收益
ll get(ll a, ll b)
{
return w - abs(b - a) * q;
}
int main()
{
int n;
cin >> n;
scanf("%s", s + 1);
for(int i = 1; i <= n; ++ i)
if(s[i] == '0') a[++ cnt] = i;
a[0] = -0x3f3f3f3f, a[cnt + 1] = 0x3f3f3f3f;
scanf("%d%d%d", &k, &w, &q);
for(int i = 1; i <= cnt; ++ i)
{
//int l = lower_bound(a + 1, a + 1 + cnt, a[i] - k) - a;
//int r = lower_bound(a + 1, a + 1 + cnt, a[i] + k) - a;
int l = find(a[i] - k), r = find(a[i] + k);
// 理想状态l = a[i] - k, 实际是a[l], 因此偏移了|a[i] - k - a[l]|天
ll max1 = max( 0ll, max( get(a[l], a[i] - k), get(a[l - 1], a[i] - k) ) );
ll max2 = max( 0ll, max( get(a[r], a[i] + k), get(a[r - 1], a[i] + k) ) );
res = max(res, max1 + max2);
}
cout << res << endl;
return 0;
}