A7390 | 活动筹备计划
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
为了准备校园科技节，$Sherry$ 需要在接下来的 $n$ 天里安排每天的筹备工作。每天可以选择以下三种任务中的一种进行：制作海报，布置场地，整理材料。
第 $i$ 天完成不同的任务会获得不同的效果值，分别为 $a_i,b_i,c_i$。
为了避免连续重复做同一种工作导致效率下降，$Sherry$ 规定相邻两天不能选择同一种任务。
此外，不同任务之间的切换还会带来额外的协同效果。设三种任务依次编号为 $1,2,3$，分别表示制作海报、布置场地、整理材料。如果第 $i-1$ 天选择了任务 $u$，第 $i$ 天选择了任务 $v$，那么第 $i$ 天还会额外获得 $w_{u,v}$ 的效果值。
请你帮 $Sherry$ 计算 $n$ 天能够获得的最大总效果值。
第 $i$ 天完成不同的任务会获得不同的效果值，分别为 $a_i,b_i,c_i$。
为了避免连续重复做同一种工作导致效率下降，$Sherry$ 规定相邻两天不能选择同一种任务。
此外，不同任务之间的切换还会带来额外的协同效果。设三种任务依次编号为 $1,2,3$，分别表示制作海报、布置场地、整理材料。如果第 $i-1$ 天选择了任务 $u$，第 $i$ 天选择了任务 $v$，那么第 $i$ 天还会额外获得 $w_{u,v}$ 的效果值。
请你帮 $Sherry$ 计算 $n$ 天能够获得的最大总效果值。
输入格式
第一行输入一个整数 $n$，表示总筹备天数。
第二行到第四行，每行输入三个整数，表示切换任务的额外协同效果。其中第 $x$ 行第 $y$ 列表示从任务 $x$ 切换到任务 $y$ 的额外收益。保证 $w_{x,x}=0$，表示不允许连续两天选择同一种任务。
接下来 $n$ 行，每行输入三个整数 $a_i,b_i,c_i$ 分别表示第 $i$ 天制作海报、布置场地、整理材料能获得的效果值。
第二行到第四行，每行输入三个整数，表示切换任务的额外协同效果。其中第 $x$ 行第 $y$ 列表示从任务 $x$ 切换到任务 $y$ 的额外收益。保证 $w_{x,x}=0$，表示不允许连续两天选择同一种任务。
接下来 $n$ 行，每行输入三个整数 $a_i,b_i,c_i$ 分别表示第 $i$ 天制作海报、布置场地、整理材料能获得的效果值。
输出格式
输出一个整数，表示最大总效果值。
输入输出样例
输入 #1
6 0 3 7 2 0 4 6 5 0 10 40 70 20 50 80 30 60 90 100 1 1 1 100 1 1 1 100
输出 #1
532
$1\le n\le 2\times 10^5$
$1\le a_i,b_i,c_i\le 10^9$
$0\le w_{x,y}\le 10^9$
$1\le a_i,b_i,c_i\le 10^9$
$0\le w_{x,y}\le 10^9$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？