AI 生成摘要
本文解决一道硬币抛掷动态规划题。针对“连续奖励”的迷之题意，采用 `cin >> c >> y[c]` 特殊输入方式。核心思路是定义状态 $f[i][j]$ 表示前 $i$ 次中连续最后一次正面为 $j$ 时的最大收益，利用两个状态转移方程求解：正面延续则累积价值，反面重置则取前序最大值。整体时间复杂度为 $O(n^2)$，需注意使用 long long 类型防溢出。

题意解毒

首先解决连续奖励的输入。

原题目中的表述很迷，导致我看了半天还以为是连续 i 次正面就奖励，代码调了半天没出来，然后直接划过去做后面一题了。

可以使用这种方式 cin >> c >> y[c]，$y[i]$ 表示连续抛 $i$ 个正面的奖励。

思路

使用动态规划，设 $f[i][j]$ 为扔到第 $i$ 次时，连续扔 $j$ 次正面的最大收益，那么状态转移方程为：

$$ f[i][0] = \max_{j = 0}^{i - 1} f[i - 1][j]$$
$$ f[i][j] = f[i - 1][j - 1] + x[i] + y[j]$$

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$，注意开 long long

然后直接看代码吧

AC 代码

#include <bits/stdc++.h>
#define int long long
/*
大佬们都这么写，我也这么写, 但是我不是大佬...
不过要注意要用signed定义主函数
*/
using namespace std;
const int N = 5005;                 // 大佬标配
int n, m, x[N], y[N], ans, f[N][N]; // f[i][j]:扔到第i次时，连续扔j次正面的最大收益
signed main()                       // 用signed定义主函数
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    for (int i = 1, c; i <= m; i++)
        cin >> c >> y[c]; // qaq，这个输入方式真的很奇妙
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < i; j++)
            f[i][0] = max(f[i][0], f[i - 1][j]);
        for (int j = 1; j <= i; j++)
            f[i][j] = f[i - 1][j - 1] + x[i] + y[j];
    } // 两个很优雅的状态转移方程
    for (int i = 0; i <= n; i++)
        ans = max(ans, f[n][i]); // 找到最大值
    cout << ans << endl;
    return 0; // 完美的结束
}