第四题 - FLIPPING AND BONUS
题目跳转：投硬币。
接下来来到了本次比赛的重头戏，题目难度也在此有了一个质的飞跃（我也不清楚这次 ABC 的难度为什么这么跳跃）。
考虑使用动态规划，定义状态 dpidp_idpi 表示第 iii 次掷硬币可以获得的最大金额。（其实这道题的状态定义有很多种，用二维的 dp 也可以通过本题，本题解暂是只提供前缀和动态规划的解法）
我们可以枚举在第 jjj 次抛置硬币时选择正面和反面的价值并取最大值。所以，对于每一次投掷硬币有两种可能的决策，分别是：
1. 硬币最终的状态时正面，得到第 iii 次投掷硬币的钱，计数器自增。因此结果就是得到 x1+x2+x3+⋯+xi−1+xix_1 + x_2 + x_3 + \cdots + x_{i-1} + x_ix1 +x2 +x3 +⋯+xi−1 +xi 元钱和 y1+y2+y3+⋯+yk−1+yk (c[k]≤i)y_1 + y_2 + y_3 + \cdots + y_{k-1} + y_k\ (c[k] \le i)y1 +y2 +y3 +⋯+yk−1 +yk (c[k]≤i) 的奖金。
2. 硬币最终的状态是反面，那么计数器就从头开始计数。因此最终可以获得的结果就为从第 jjj 次投硬币时可以获得的最大金额 dpjdp_jdpj 加上在区间 [j+2,i][j+2, i][j+2,i] 投币全是正面所获的的金额（因为第 j+1j+1j+1 次投币不会获得任何的奖励）(x1+x2+x3+⋯+xi−1+xi)−(x1+x2+x3+⋯+xj+xj+1)(x_1 + x_2 + x_3 + \dots + x_{i-1} + x_i) - (x_1 + x_2 + x_3 + \cdots + x_j + x_{j+1})(x1 +x2 +x3 +⋯+xi−1 +xi )−(x1
+x2 +x3 +⋯+xj +xj+1 ) 再加上前 i−j−1i-j-1i−j−1 次计数器的奖励金额 (y1+y2+y3+⋯+yk−1+yk (c[k]≤i−j−1)(y_1 + y_2 + y_3 + \cdots + y_{k-1} + y_k\ (c[k] \le i-j-1)(y1 +y2 +y3 +⋯+yk−1 +yk (c[k]≤i−j−1) 。
可以发现，我们可以通过开设两个前缀和数组来优化算法，分别约定 suma,sumb\mathtt{suma, sumb}suma,sumb 分别表示前 iii 次投币全都是正面所获的的金额和计数器的奖励金额。因此最后的状态转移方程时可以写成：
dpi=max(dpi,dpj+sumai−sumaj****umbi−j−1)dp_i = \max(dp_i, dp_j + suma_i - suma_{j+1} + sumb_{i-j-1}) dpi =max(dpi ,dpj +sumai −sumaj+1 +sumbi−j−1 )
备注：十年 OI 一场空，不开 long long 见祖宗。请大家务必开 long long。本题的时间复杂度为 Θ(N+N22)\Theta(\dfrac{N+N^2}{2})Θ(2N+N2 )。
周后，本题的 AC 代码如下：
