A6919. 跳跃假期
编程题
普及/提高-
知识点
题目描述
小 K 打算进行一个为期 $N$ 天的“跳跃假期”。每天他都可以从三项活动中选择一项参加。
第 $i$ 天如果选择活动 A/B/C，将分别获得愉悦值 $a_i$、$b_i$、$c_i$。
但为了不过度疲劳，相邻两天不能选择同一种活动。请你帮他安排一个计划，使得 $N$ 天的总愉悦值最大。
第 $i$ 天如果选择活动 A/B/C，将分别获得愉悦值 $a_i$、$b_i$、$c_i$。
但为了不过度疲劳，相邻两天不能选择同一种活动。请你帮他安排一个计划，使得 $N$ 天的总愉悦值最大。
输入格式
第一行一个整数 $N$。
接下来 $N$ 行，每行三个整数 $a_i, b_i, c_i$，表示第 $i$ 天三项活动的愉悦值。
接下来 $N$ 行，每行三个整数 $a_i, b_i, c_i$，表示第 $i$ 天三项活动的愉悦值。
输出格式
输出一个整数，为在不违反“相邻两天不能同项”的条件下，$N$ 天可获得的最大总愉悦值。
输入输出样例
输入 #1
3 10 1 1 1 10 1 1 1 10
输出 #1
30
输入 #2
6 10 1 1 1 10 1 1 1 10 10 1 1 1 10 1 1 1 10
输出 #2
60
说明/提示
$1 \le N \le 10^5$
$0 \le a_i, b_i, c_i \le 10^4$
对于样例一：
一种最优方案是：第 $1$ 天选 $A（10）$，第 $2$ 天选 $B（10）$，第 $3$ 天选 $C（10）$，总和为 $30$。任意相邻两天都未重复同一活动。
对于样例二：
按 $A \to B \to C \to A \to B \to C$ 选择即可，每天都拿到“当天的最大值”，且从不连续选同一项，得到总和 $60$。
$0 \le a_i, b_i, c_i \le 10^4$
对于样例一：
一种最优方案是：第 $1$ 天选 $A（10）$，第 $2$ 天选 $B（10）$，第 $3$ 天选 $C（10）$，总和为 $30$。任意相邻两天都未重复同一活动。
对于样例二：
按 $A \to B \to C \to A \to B \to C$ 选择即可，每天都拿到“当天的最大值”，且从不连续选同一项，得到总和 $60$。