代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
int n;
char A[N];
int T[N],M[N];
int main(){scanf("%d",&n);scanf("%s",A + 1);ll k,w,q;scanf("%lld%lld%lld",&k,&w,&q);int tT = INT_MIN;for(int i = 1;i <= n;i++){if(A[i] == '0') tT = i;T[i] = tT;}int tN = INT_MAX;for(int i = n;i;i--){if(A[i] == '0') tN = i;M[i] = tN;}ll ans = 0;for(int i = 1;i <= n + 1;i ++){if(A[i] == '1') continue;ll R = 0;ll l = i - k,r = i + k;R+=max(0ll,w-(ll)q*min(abs(T[max(l,1ll)]-l),abs(M[max(l,1ll)]-l)));  // 枚举第T[i-k]和M[i-k]R+=max(0ll,w-(ll)q*min(abs(T[min(r,(ll)n)]-r),abs(M[min(r,(ll)n)]-r))); // 枚举第T[i+k]和M[i+k]ans = max(ans,R);}printf("%lld\n",ans);return 0;
}

题目（关键信息）

1.疫苗最多接种三针，且只有后两针接种才能提升手速，且一天最多只能打一针

2.后一针疫苗与前一针疫苗之间相隔k天对手速的提升最为明显，每偏离一天则效果会相应减少，更具体地，设定相隔k天对手速的提升为w,如果两针实际相隔了p天，每偏离一天则效果减少q的话，则后一针疫苗实际对人手速的影响为$w-|k-p|\ast q$

n天以后就是伸阳站的比赛了，所以九峰只需要考虑n天内疫苗的接种，但这n天中有一些牛客的小比赛，众所周知九峰对于牛客的比赛从不缺席，所以在有比赛的日子里他不会接种疫苗，希望你能帮他合理安排接种使得他手速提升最大

分析

这道题可以使用动态规划来实现。
但其最终代码可以优化成““看不出是动态规划”的样子。

以下我使用动态规划的思路分析这道题。

我们要找的是打疫苗后的最优手速，取得最优手速时，可能打了零针、一针、两针或三针。
因为$n\le 10^6$，所以时间复杂度必须在$O(n^2)$以下。

限于时间复杂度，所以我们猜测无法采用类似于01背包的$O(n^2)$复杂度的处理方法，应该优先考虑在线性时间内获得最优值。

因此这里的状态表示为：
$f[i]$表示选择了第$i$天打疫苗的方案可能获得的最大手速（这个状态的解释并不全面，请往下看）。

由状态表示不难看出，如果第$i$天有牛客赛，即A[i] == '1'，那么$f[i]=0$。

当A[i] == '0'时，即当天没有牛客赛，允许打疫苗，当天可能是第一次、第二次或是第三次打疫苗。由于手速与打疫苗的间隔有关，所以我们应当优先考虑第$i-k$天和第$i+k$天的情况。

那问题来了，为什么没有考虑第$i-2\ast k$天和第$i+2\ast k$天的情况呢？
这个我们放到后面解释

如果第$i-k$天和第$i+k$天也允许打疫苗，那么便必定有最佳的手速。
但可能出现$i-k<=0$ 或 $i+k>n$ 或有牛客赛的情况，导致该天不能打疫苗。根据题意，此时最优的方案是选择最靠近$i-k$和$i+k$的能打疫苗的日子了。

此时可以初始化两个数组T和M：

• $T[i]$表示在第$i$天之前（包括第$i$天）最靠近第$i$天的没有牛客赛的日子。
• $M[i]$表示在第$i$天之后（包括第$i$天）最靠近第$i$天的没有牛客赛的日子。

所以此时选择第$i$天的最优手速为：
$$f_i=max(选择(i,T_{i-k},T_{i+k}),选择(i,T_{i-k},M_{i+k}),选择(i,M_{i-k},Ti+k),选择(i,M_{i-k},M_{i+k}))$$

可以看到，本题虽然可以写出状态方程，但该状态方程不存在““状态转移”的特点，即当前的$f[i]$不需要借助$f[k](k\ne i)$得到，这便使得代码可以最终优化成““看不出动态规划”的情况。

由于最优解必定存在于数组$f$中，所以我们可以在逐个计算状态的同时找出最优解。有因为$f[i]$的值不依赖域其他状态，所以我们不需要使用数组将每一天的状态保存起来，只要逐个枚举找出最优解即可。

为什么没有考虑第$i-2\ast k$天和第$i+2\ast k$天的情况呢

如果按照严格的状态定义，我们在枚举第$i$天时，应该枚举第$i-2\ast k$天和第$i+2\ast k$天的情况。

但我们发现，这样枚举不仅会使代码更加复杂，而且会导致多次重复枚举了同一个方案，提高的时间复杂度。在计算第$i-k$天最优状态时，自然会枚举到选择了$i-2\ast k$天的方案，$i+2\ast k$同理。因此，我们可以在计算第$i$天是忽略第$i-2\ast k$天和第$i+2\ast k$天的情况——最优方案依然会被枚举到。

错误原因

没有使用合适的状态表示及进行状态简化，导致代码实现难度过大。

注：我使用动态规划的思路对本题进行理解和思考，并不意味着本题必须通过动态规划进行分析。

---

题目链接
原创不易，感谢支持！