背包猫猫赚钱钱
油菜花题目描述
猫猫计划和咪咪来一场浪漫的约会,通过投硬币的游戏来为自己赚取金钱。猫猫会掷硬币N次。 他还有一个计数器,最初显示:0.根据第 i 次抛硬币的结果,会发生以下情况:
- 如果硬币正面向上:猫猫计数器的价值+1,并接收Xi元。
- 如果硬币反面向上:他将计数器的价值重置为0,而收不到钱。
此外,猫猫还有M种连胜奖金。第 i 种连胜奖金奖励 Yi 元当每次计数器显示 Ci 时。
你的任务是找到猫猫可以收到的最大金额,让猫猫可以和心动的咪咪约会。
输入描述
N M
X1 X2 … XN
C1 Y1
C2 Y2
.
.
.
CM YM
输出描述
打印猫猫收到的最大的金额。
用例输入 1
1 2 3 4 5
| 6 3 2 7 1 8 2 8 2 10 3 1 5 5
|
用例输出 1
提示
1≤M≤N≤5000
1≤Xi≤109
1≤Ci≤N
1≤Yi≤109
C1,C2,C3,都是不同的
所有的输入都是整数
代码
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| #include<iostream> #include<bits/stdc++.h> using namespace std;
long long dp[5010][5010];
long long c[5010],a[5010]; long long n,m,b;
int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } while(m--){ cin>>b; cin>>c[b]; } for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++) { dp[i][j]=dp[i-1][j-1]+a[i]+c[j]; } dp[i][0]=0; for(int k=0;k<i;k++){ dp[i][0]=max(dp[i][0],dp[i-1][k]); } } long long res=0; for(int j=0;j<=n;j++){ res=max(res,dp[n][j]); } cout<<res<<endl; return 0; }
|