#P51028. 「JOISC 2015 Day 3」Card Game Is Great Fun
「JOISC 2015 Day 3」Card Game Is Great Fun
题目描述
译自 JOISC 2015 Day3 T2「Card Game Is Great Fun」。
有 张扑克堆成一个栈,从上往下第 张花色是 ,点数是 ,价值是 。有这样一个操作,每次可以选择拿走从上往下第 张或者第 张,拿走的牌必须和上一次拿走的花色或者点数一样。
请问如何拿牌,才能使得拿出来的牌的价值和最大。
输入格式
第一行包含一个整数 ,表示牌的个数。
接下来 行,第 行包含三个整数 , 和 ,表示从上往下第 张花色是 ,点数是 ,价值是 。
输出格式
输出一个整数表示最大价值和。
样例 1
5
1 3 2
4 2 9
1 4 6
2 3 3
2 2 1
15
我们用 表示花色为 ,点数为 ,价值为 的牌。那么最优的操作序列如下:
- 选第 张牌 ,得到分数为 。
- 选第 张牌 ,得到分数为 。
- 选第 张牌 ,得到分数为 。
- 选第 张牌 ,得到分数为 。
8
11 5 31
2 8 19
2 9 2
11 8 45
4 8 22
4 2 23
6 9 58
6 2 5
160
数据范围与提示
对于全部数据,满足 。
本题共有 个子任务。每个子任务的分数和附加限制如下:
Subtask | 附加限制 | 分数 |
---|---|---|
1 | 10 | |
2 | 15 | |
3 | 无附加限制 | 75 |