#AT3. Vacation
Vacation
[C] Vacation(dp_c)
来源: AtCoder Educational DP Contest - Problem C 原题时限:2 秒 / 内存:1024 MB
题目描述
太郎的暑假明天开始,他决定现在就制定好计划。
假期共有 天。对于每个 (),太郎会在第 天从下面的活动中选择一项来做:
- A:去海里游泳,获得 点幸福值。
- B:去山里抓虫子,获得 点幸福值。
- C:在家做作业,获得 点幸福值。
由于太郎很容易厌倦,他不能连续两天或更多天做同一项活动。
求太郎能获得的最大幸福值总和。
输入格式
输入由标准输入按以下格式给出:
N
a_1 b_1 c_1
a_2 b_2 c_2
:
a_N b_N c_N
输出格式
输出太郎能获得的最大幸福值总和。
数据范围
- 输入中的所有值均为整数。
样例 1
输入:
3
10 40 70
20 50 80
30 60 90
输出:
210
样例 2
输入:
1
100 10 1
输出:
100
样例 3
输入:
7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1
输出:
46