U523579 抛硬币 题解

#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; // 完美的结束
}