#2179. Straps

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

Straps

Straps

题目描述

Japanese Olympiad in Informatics 2013/2014 Spring Training Camp/Qualifying Trial March 19–25, 2014, Komaba/Yoyogi, Tokyo Contest Day 4 – Straps ストラップ(Straps) JOI 君は,携帯電話に取り付けるためのストラップをN 個持っている.ストラップには1 からN までの 番号が付けられている.JOI 君は,これらのストラップのうちいくつかを携帯電話に取り付けようとして いる. JOI 君の持っているストラップは少し変わっていて,いくつかのストラップには,他のストラップを取 り付けるための端子が何個か付いている.それぞれのストラップは,携帯電話に直接取り付けるか,ある いは他のストラップの端子に取り付けることができる.携帯電話に直接取り付けられるストラップは1 個 までである. また,それぞれのストラップには,取り付けたときに得られる嬉しさが決まっている.この嬉しさは1 つの整数で表される.JOI 君が嫌いなストラップもあり,その場合は嬉しさは負の値になる. JOI 君は,携帯電話につながっているストラップの嬉しさの総和を最大化したい.ただし,必ずしもす べての端子にストラップが取り付けられている必要はなく,ストラップを1 つも取り付けなくてもかまわ ない. 課題 JOI 君の持っているN 個のストラップの情報が与えられる.適切にストラップを取り付けたとき,携帯 電話につながっているストラップの嬉しさの総和の最大値を求めるプログラムを作成せよ. 入力 標準入力から以下のデータを読み込め. • 1 行目には,整数N が書かれている.N はストラップの個数を表す. • 続くN 行のうちのi 行目(1 ≦i ≦N) には,整数Ai, Bi が空白を区切りとして書かれている.これはス トラップi には端子がAi 個あり,そのストラップを取り付けたときの嬉しさがBi であることを表す. 出力 標準出力に,携帯電話につながっているストラップの嬉しさの総和の最大値を表す整数を1 行で出力せよ. 制限 すべての入力データは以下の条件を満たす. • 1 ≦N ≦2 000. ストラップ– 1 / 3 Japanese Olympiad in Informatics 2013/2014 Spring Training Camp/Qualifying Trial March 19–25, 2014, Komaba/Yoyogi, Tokyo Contest Day 4 – Straps • 0 ≦Ai ≦N (1 ≦i ≦N). • −1 000 000 ≦Bi ≦1 000 000 (1 ≦i ≦N). 小課題 小課題1 [5 点] • N ≦15 を満たす. 小課題2 [5 点] • Bi ≧0 (1 ≦i ≦N) を満たす. 小課題3 [45 点] • Ai ≦15 (1 ≦i ≦N) を満たす. 小課題4 [45 点] 追加の制限はない. 入出力例 入力例1 出力例1 5 5 0 4 2 -2 1 -1 0 1 0 3 この入力の場合,次のようにストラップを取り付けると嬉しさの総和は5 となり,これが最大となる. • ストラップ2 を,携帯電話に直接取り付ける. • ストラップ1 を,ストラップ2 の端子に取り付ける. • ストラップ5 を,ストラップ2 の端子に取り付ける. ストラップ– 2 / 3 Japanese Olympiad in Informatics 2013/2014 Spring Training Camp/Qualifying Trial March 19–25, 2014, Komaba/Yoyogi, Tokyo Contest Day 4 – Straps 入力例2 出力例2 6 0 2 -3 3 -1 0 -4 0 -2 1 -3 4 -1 この入力の場合,どのストラップの嬉しさも0 未満である.よって,ストラップを1 つも取り付けない 場合に嬉しさの総和が最大となる. 入力例3 出力例3 15 43417 1 -4034 1 3406 0 6062 4 -6824 0 9798 0 4500 0 -1915 1 2137 0 9786 0 7330 0 -9365 2 2730 0 -5797 0 6129 0 8925 ストラップ– 3 / 3

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5
0 4
2 -2
1 -1
0 1
0 3
5

样例 2

6
2 -3
3 -1
0 -4
0 -2
1 -3
4 -1
0