#2177. Card Game Is Great Fun

    ID: 2177 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1553来源:qoj.ac数据:公开样例贪心

Card Game Is Great Fun

Card Game Is Great Fun

题目描述

Japanese Olympiad in Informatics 2014/2015 Spring Training Camp/Qualifying Trial March 19–25, 2015, Komaba/Yoyogi, Tokyo Contest Day 3 – Card Game Is Great Fun とてもたのしいカードゲーム(Card Game Is Great Fun) アンナは友人のブルーノとよくカードゲームで遊んでいたが,2 人で行うゲームには飽きてしまったの で1 人でできるカードゲームを考えた. このゲームの開始時には,さまざまな色のカードがN 枚一列に並んでおり,それぞれのカードには整数 が1 つ書かれている.それぞれのカードの色は整数で表される.また,それぞれのカードには価値が定まっ ている.ゲーム開始時に列の先頭からi 番目(1 ≦i ≦N) にあるカードの色はCi であり,書かれている整 数はAi である.そのカードの価値はVi である. カードの列からカードを1 枚選んで取り除き,山札に加えていくという操作を繰り返すことでゲームを 行う.はじめ,山札にカードはなく,その状態からアンナは以下の操作を繰り返す. • 操作:カードの列の先頭から1 番目もしくは3 番目のカードを選ぶ.ただし,操作を行う前に山札 にカードが存在するときには,山札の一番上のカードと,色または書かれている整数の少なくとも一 方が一致しているようなカードしか列から選ぶことができない.選んだカードを列から取り除いて, 山札の一番上に加える. 操作によって選ぶことのできるカードが無くなった時点でゲームは終了する.ゲームが終了した時点で 山札にあるカードの価値の合計がアンナの得点となる. このゲームにおいてアンナが得ることのできる得点の最大値はいくらになるだろうか. 課題 ゲーム開始時に並んでいるカードの情報が与えられたとき,このゲームにおいてアンナが得ることので きる得点の最大値を求めるプログラムを作成せよ. 入力 標準入力から以下のデータを読み込め. • 1 行目には,整数N が書かれている.これは,ゲーム開始時にカードがN 枚並んでいることを表す. • 続くN 行のうちのi 行目(1 ≦i ≦N) には,3 個の整数Ci, Ai, Vi が空白を区切りとして書かれてい る.これは,ゲーム開始時に列の先頭からi 番目にあるカードの色がCi,書かれている整数がAi,価 値がVi であることを表す. 出力 標準出力に,このゲームにおいてアンナが得ることのできる得点の最大値を表す整数を1 行で出力せよ. とてもたのしいカードゲーム– 1 / 3 Japanese Olympiad in Informatics 2014/2015 Spring Training Camp/Qualifying Trial March 19–25, 2015, Komaba/Yoyogi, Tokyo Contest Day 3 – Card Game Is Great Fun 制限 すべての入力データは以下の条件を満たす. • 1 ≦N ≦500. • 1 ≦Ci ≦500 (1 ≦i ≦N). • 1 ≦Ai ≦500 (1 ≦i ≦N). • 1 ≦Vi ≦1 000 000 (1 ≦i ≦N). 小課題 小課題1 [10 点] • N ≦20 を満たす. 小課題2 [15 点] • N ≦50 を満たす. 小課題3 [75 点] 追加の制限はない. とてもたのしいカードゲーム– 2 / 3 Japanese Olympiad in Informatics 2014/2015 Spring Training Camp/Qualifying Trial March 19–25, 2015, Komaba/Yoyogi, Tokyo Contest Day 3 – Card Game Is Great Fun 入出力例 入力例1 出力例1 5 15 1 3 2 4 2 9 1 4 6 2 3 3 2 2 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 出力例2 8 160 11 5 31 2 8 19 2 9 2 11 8 45 4 8 22 4 2 23 6 9 58 6 2 5 とてもたのしいカードゲーム– 3 / 3

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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

样例 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
160