AtCoder Beginner Contest 261(D - Flipping and Bonus)

[原题链接](https://atcoder.jp/contests/abc261/tasks/abc261_d "原题链接")

### 题意
现投掷1枚硬币n次，可能的结果为：

1. value++, money+=x[i];
2. value=0, money=0;
另，value达到ci时,money+=yi
求投掷n次硬币可能达到的最大money为多少

### 思路
简单dp,直接来个状态转移
f[i][j]: 当前走到i, 有连续j次正面朝上的money
然后按照第i次正面朝上/朝下，分别转移即可

```cpp
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 5005;
int n, m;
int v[N], x[N];
int f[N][N]; //前i次掷骰子的连胜次数为j的最大得分

signed main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)   cin >> x[i];
    
    for (int i = 1; i <= m; i ++) {
        int a, b;
        cin >> a >> b;
        v[a] = b;
    }

for (int i = 1; i <= n; i ++) {
        //第i次正面朝上
        for (int j = 0; j <= i; j ++) 
            f[i][j] = f[i-1][j-1] + x[i] + v[j];  
        
        //第i次正面朝下
        //在i次之前所有可能的情况中,记录最大值
        for (int j = 0; j < i; j ++)
            f[i][0] = max (f[i][0], f[i-1][j]);
    }

int ans = 0;
    for (int i = 0; i <= n; i ++)   ans = max (ans, f[n][i]);
    cout << ans << endl;
}

//1. value++, money+=x[i];
//2. value=0, money=0;
//value达到ci时,money+yi

//dp
//max (f[n][0], f[n][1],...,f[n][n]);
//f[i][j]: 当前走到i, 有连续j次正面朝上的money

```
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m;
LL f[5005][5005], a[5005], b[5005], ans, maxn;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    LL u, v;
    for (int i = 1; i <= m; i++)
        scanf("%lld%lld", &u, &v), b[u] += v;
    f[1][1] = a[1] + b[1];
    for (int i = 2; i <= n; i++) {
        maxn = 0;
        for (int j = 1; j <= i; j++)
            f[i][j] = f[i - 1][j - 1] + a[i] + b[j], maxn = max(f[i - 1][j], maxn);
        f[i][0] = maxn;
    }
    for (int j = 0; j <= n; j++)
        ans = max(ans, f[n][j]);
    printf("%lld", ans);
    return 0;
}

```