分数: 600 点
问题陈述
我们有 3N 卡从左到右排列成一排,其中每张卡之间都有一个整数 上面写着 1 和 N (含)。写在上面的整数 i左起第一张牌是 A_i.
您将执行以下操作 N-1 次:
- 按照您喜欢的任意顺序重新排列最左边的五张牌,然后移除最左边的三张牌。如果这三张卡片上写的整数都相等,您将获得 1 点。
在这些之后 N-1 运算,如果剩余三张牌上写的整数都相等,你将获得 1 补充一点。
找出您可以获得的最大分数。
约束
- 1 \leq N \leq 2000
- 1 \leq A_i \leq N
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 \cdots A_{3N}
输出
打印您可以获得的最大分数。
示例输入 1
2 1 2 1 2 2 1
示例输出 1
2
让我们重新排列最左边的五张卡片,以便六张卡片上写的整数将是 2\ 2\ 2\ 1\ 1\ 1 从左到右。
然后,取出最左边的三张牌,它们都有相同的整数 2,获得 1 点。
现在,剩下的卡片上写的整数是 1\ 1\ 1.
由于这三张牌具有相同的整数 1,我们获得 1 更多一点。
这样,我们可以获得 2 点 - 这是可能的最大值。
示例输入 2
3 1 1 2 2 3 3 3 2 1
示例输出 2
1
示例输入 3
3 1 1 2 2 2 3 3 3 1
示例输出 3
3