#3002. 「JOISC 2015 Day 3」Card Game Is Great Fun

内存限制:1024 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Chiaki

题目描述

译自 JOISC 2015 Day3 T2「Card Game Is Great Fun」。

N 张扑克堆成一个栈,从上往下第 i 张花色是 C_i ,点数是 A_i ,价值是 V_i 。有这样一个操作,每次可以选择拿走从上往下第 1 张或者第 3 张,拿走的牌必须和上一次拿走的花色或者点数一样。

请问如何拿牌,才能使得拿出来的牌的价值和最大。

输入格式

第一行包含一个整数 N ,表示牌的个数。

接下来 N 行,第 i 行包含三个整数 C_i A_i V_i ,表示从上往下第 i 张花色是 C_i ,点数是 A_i ,价值是 V_i

输出格式

输出一个整数表示最大价值和。

样例

样例输入 1

5
1 3 2
4 2 9
1 4 6
2 3 3
2 2 1

样例输出 1

15

样例解释 1

我们用 (c, a, v) 表示花色为 c ,点数为 a ,价值为 v 的牌。那么最优的操作序列如下:

  1. 选第 1 张牌 (1, 3, 2) ,得到分数为 2
  2. 选第 3 张牌 (2, 3, 3) ,得到分数为 3
  3. 选第 3 张牌 (2, 2, 1) ,得到分数为 1
  4. 选第 1 张牌 (4, 2, 9) ,得到分数为 9

样例输入 2

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

样例输出 2

160

数据范围与提示

对于全部数据,满足 1 \le N \le 500, 1 \le C_i, A_i \le 500, 1 \le V_i \le 10^6

本题共有 3 个子任务。每个子任务的分数和附加限制如下:

Subtask 附加限制 分数
1 N \le 20 10
2 N \le 50 15
3 无附加限制 75