投硬币｜动态规划前缀和优化

第四题 - Flipping and Bonus

题目跳转：投硬币。

接下来来到了本次比赛的重头戏，题目难度也在此有了一个质的飞跃（我也不清楚这次 ABC 的难度为什么这么跳跃）。

考虑使用动态规划，定义状态 $dp_i$ 表示第 $i$ 次掷硬币可以获得的最大金额。（其实这道题的状态定义有很多种，用二维的 dp 也可以通过本题，本题解暂是只提供前缀和动态规划的解法）

我们可以枚举在第 $j$ 次抛置硬币时选择正面和反面的价值并取最大值。所以，对于每一次投掷硬币有两种可能的决策，分别是：

1. 硬币最终的状态时正面，得到第 $i$ 次投掷硬币的钱，计数器自增。因此结果就是得到 $x_1 + x_2 + x_3 + \cdots + x_{i-1} + x_i$ 元钱和 $y_1 + y_2 + y_3 + \cdots + y_{k-1} + y_k\ (c[k] \le i)$ 的奖金。
2. 硬币最终的状态是反面，那么计数器就从头开始计数。因此最终可以获得的结果就为从第 $j$ 次投硬币时可以获得的最大金额 $dp_j$ 加上在区间 $[j+2, i]$ 投币全是正面所获的的金额（因为第 $j+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})$ 再加上前 $i-j-1$ 次计数器的奖励金额 $(y_1 + y_2 + y_3 + \cdots + y_{k-1} + y_k\ (c[k] \le i-j-1)$ 。

可以发现，我们可以通过开设两个前缀和数组来优化算法，分别约定 $\mathtt{suma, sumb}$ 分别表示前 $i$ 次投币全都是正面所获的的金额和计数器的奖励金额。因此最后的状态转移方程时可以写成：

$$dp_i = \max(dp_i, dp_j + suma_i - suma_{j+1} + sumb_{i-j-1})$$

备注：十年 OI 一场空，不开 long long 见祖宗。请大家务必开 long long。本题的时间复杂度为 $\Theta(\dfrac{N+N^2}{2})$。

周后，本题的 AC 代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
long long dp[5005],x[5005],c[5005],y[5005],suma[5005],sumb[5005],m,n,cnt;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>x[i];
        suma[i]=suma[i-1]+x[i];
    }
    for(int i=1;i<=m;i++){
        int a, b;
        cin >> a >> b;
        c[a] = b;
    }
    for (int i=1; i<=5000; i++){
        sumb[i]=sumb[i-1]+c[i];
    }
    for(int i=1;i<=n;i++){
        dp[i]=suma[i]+sumb[i];
        for(int j=1;j<i;j++){
            // 状态转移方程的推导见原文。
        	dp[i]=max(dp[i],dp[j]+suma[i]-suma[j+1]+sumb[i-j-1]);
        }
    }
    cout<<dp[n];
	return 0;
}