题解

Atcoder Beginner Contest 261 Problem D 题解

题目链接：https://atcoder.jp/contests/abc261/tasks/abc261_d

题目大意

高桥将掷硬币$N$次。 他还有一个计数器，最初显示为$0$。
根据第$i$次抛硬币的结果，他将执行以下操作：

• 如果是正面：高桥会将计数器的值增加$1$并收到$X_i$日元。
• 如果是反面：高桥会将计数器的值变为$0$且不会受到日元。

此外，还有$M$中类型的奖励。当计数器的值为$C_i$时可获得第$i$种连胜奖金奖励$Y_i$.
试求出高桥能收到的最大金额。

样例输入1

6 3
2 7 1 8 2 8
2 10
3 1
5 5

样例输出1

48

样例输入2

3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000

样例输出2

5000000000

数据范围

• $1 \leq M \leq N \leq 5000$
• $1 \leq X_i \leq 10^9$
• $1 \leq C_i \leq N$
• $1 \leq Y_i \leq 10^9$
• $C_1 \neq C_2 \neq C_3 \neq \cdots \neq C_M$
• 所有输入都为整数。

解析

本题使用动态规划算法求解，解法如下：
令 $f_{i,j}$ 表示将硬币抛$i$次且计数器值为$j$时的最大金额，则有：

• 若$j=0$，则：

  令$k$为$1$至$i-1$中任意数，则有：$f_{i,j} = max(f_{i-1,k})$

• 若$1 \leq j \leq i$，则：

  $f_{i,j} = max(f_{i-1,j-1}+X_i)$

• 令$k$为$1$至$M$中任意数，若$j=C_k$，则有：

  $f_{i,j}+=Y_k$

对于第三种情况，可在枚举所有$j$后单独枚举所有$k$并将所有$f_{i,C_k}$加上$Y_k$即可。

代码实现

以上算法代码实现如下：

#include<bits/stdc++.h>
using namespace std;
#define N 5005
int n,m;
long long f[N][N],x[N],c[N],y[N];  //f[i][j]:共抛出i次且计数器为j
int main(){
    memset(f,-0x3f,sizeof f);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&x[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d %d",&c[i],&y[i]);
    }
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int k=1;k<i;k++) f[i][0]=max(f[i][0],f[i-1][k]);
        for(int j=1;j<=i;j++){
            f[i][j]=max(f[i][j],f[i-1][j-1]+x[i]);
        }
        for(int k=1;k<=m;k++){
            f[i][c[k]]+=y[k];
        }
    }
    long long ans=0;
    for(int i=0;i<=n;i++){
        ans=max(f[n][i],ans);
    }
    cout<<ans;
    return 0;
}