A3119 | 投硬币
时间限制2s
内存限制256MB
通过 / 提交0/0
题目描述
时间限制:2000ms
内存限制:256MB
小码君接下来会投掷硬币 $N$ 次。他还有一个计数器,初始值为 0。
根据第 $i$ 次掷硬币的结果:
- 如果是正面:将计数器的值增加 $1$,并获得 $X_i$ 元。
- 如果是反面:将计数器的值重置为 $0$,并且不会得到钱。
另外,还有 $M$ 种额外奖金。
第 $i$ 种奖金会在计数器的值为 $C_i$ 时,每次奖励 $Y_i$ 元。
求小码君能获得的最大金额。
$\large{数据范围}$
- $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,C_2,\ldots,C_M$ 互不相等。
- 所有输入数值均为整数。
输入格式
对于每个测试文件格式如下:
$\tt{X_1\ X_2\ \ldots\ X_N}$
$\tt{C_1\ Y_1}$
$\tt{C_2\ Y_2}$
$\tt{\vdots}$
$\tt{C_M\ Y_M}$
$\tt{N\ M}$
$\tt{X_1\ X_2\ \ldots\ X_N}$
$\tt{C_1\ Y_1}$
$\tt{C_2\ Y_2}$
$\tt{\vdots}$
$\tt{C_M\ Y_M}$
输出格式
对于每个测试文件输出小码君能够获得的最大金额。
输入输出样例
输入 #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$:
若投硬币的结果依次为正,正,反,正,正,正:
- 在第 $1$ 次掷硬币中,为正面。将计数器的值从 $0$ 改为 $1$ ,获得 $2$ 元。
- 在第 $2$ 次抛硬币中,为正面。将计数器的值从 $1$ 改为 $2$ ,得到 $7$ 元。此外,还可以获得 $10$ 元的奖金。
- 在第 $3$ 次抛硬币中,为反面。将计数器的数值从 $2$ 改为 $0$ 。
- 在第 $4$ 次抛硬币中,为正面。将计数器的值从 $0$ 改为 $1$ ,得到 $8$ 元。
- 在第 $5$ 次抛硬币中,为正面。将计数器的值从 $1$ 改为 $2$ ,得到 $2$ 元。此外,还能获得 $10$ 元的额外奖金。
- 在 $6$ 次抛硬币中,为正面。将计数器的值从 $2$ 改为 $3$ ,即可获得 $8$ 元。此外,还能获得 $1$ 元的额外奖励。
在这种情况下,总共获得可以获得 $2+(7+10)+0+8+(2+10)+(8+1)=48$ 元,这是可能获得的最高数额。
请注意,每次计数器显示 $C_i$ 时,都可以获得 $Y_i$ 元奖金。
顺便提一下,如果他在所有掷硬币的 $6$ 中都得到了正面,那么他只能得到 $2+(7+10)+(1+1)+8+(2+5)+8=44$ 元。
样例 $2$:
请注意,答案可能会超出 $32$ 位整数类型。
若投硬币的结果依次为正,正,反,正,正,正:
- 在第 $1$ 次掷硬币中,为正面。将计数器的值从 $0$ 改为 $1$ ,获得 $2$ 元。
- 在第 $2$ 次抛硬币中,为正面。将计数器的值从 $1$ 改为 $2$ ,得到 $7$ 元。此外,还可以获得 $10$ 元的奖金。
- 在第 $3$ 次抛硬币中,为反面。将计数器的数值从 $2$ 改为 $0$ 。
- 在第 $4$ 次抛硬币中,为正面。将计数器的值从 $0$ 改为 $1$ ,得到 $8$ 元。
- 在第 $5$ 次抛硬币中,为正面。将计数器的值从 $1$ 改为 $2$ ,得到 $2$ 元。此外,还能获得 $10$ 元的额外奖金。
- 在 $6$ 次抛硬币中,为正面。将计数器的值从 $2$ 改为 $3$ ,即可获得 $8$ 元。此外,还能获得 $1$ 元的额外奖励。
在这种情况下,总共获得可以获得 $2+(7+10)+0+8+(2+10)+(8+1)=48$ 元,这是可能获得的最高数额。
请注意,每次计数器显示 $C_i$ 时,都可以获得 $Y_i$ 元奖金。
顺便提一下,如果他在所有掷硬币的 $6$ 中都得到了正面,那么他只能得到 $2+(7+10)+(1+1)+8+(2+5)+8=44$ 元。
样例 $2$:
请注意,答案可能会超出 $32$ 位整数类型。
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?