AI 生成摘要
本文以连续奖励问题的动态规划解法为例，阐述了如何通过理解题意将连续正面次数映射为输入。文章给出了定义状态、推导状态转移方程的详细思路，分析了题目需注意的`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 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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; // 完美的结束
}