AI 生成摘要
该博客分享了参加某次编程竞赛时，遇到一道投掷硬币的连续奖励问题的经历。原题描述不清，导致博主一度误解题意。问题要求实现动态规划，使用二维数组$f[i][j]$表示投掷到第$i$次、连续$j$次正面的最大收益。状态转移方程考虑了不保留连续性或保留连续性两种情况，时间复杂度为$O(n^2)$，空间也类似。博主提供的代码巧妙处理了输入，并通过双层循环实现了状态转移，成功得到答案。

题意解毒

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

原题目中的表述很迷，导致我看了半天还以为是连续 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; // 完美的结束
}