問題一覧 > 通常問題

No.119 旅行のツアーの問題

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 84
作問者 : nmnmnmnmnmnmnm
19 ProblemId : 7 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:49

問題文

N個の国があります。
国は０番目からN-1番目と数えます。
A君はN個の国から旅行に行きたい国を選びました。
A君は必ず小さい番目の国から順に旅行に出かけます。

旅行会社に行くと各国にはそれぞれ１つのツアーがあるようでした。
ただし、旅行会社のツアーというものは良いものもあれば、
返って自由度が減って嫌なものもあります。
ツアーに行くか行かないかで満足度が設定されています。

また、旅行会社の人が言うには、あるツアーに行ったら別の国のツアーにも参加しないといけない。
という条件がいくつかあるようでした。
例えば、

・x番目の国のツアーに行ったらy番目の国のツアーに行かなければならない(x<y)

というような条件です。
もし、x番目の国とy番目の国の両方に行くならこの条件が発生します。
A君は理由はよくわからないけど条件を呑むことにしました。
旅行の全行程を通して満足度は加算されていきます。
A君はより多くの満足度を得たいです。
最大の満足度を答えなさい。

すなわち、それぞれ条件をみたすのなら、
・x番目の国に行かない。
・x番目の国に行くけど、ツアーには参加しない。
・x番目の国に行き、ツアーにも参加する。
のどれかの選択ができるということである。

入力

N
B0 C0
⋮
Bn−1 Cn−1
M
D0 E0
⋮
Dm−1 Em−1

Nは正の整数。1≤N≤40。
以下、N個の国のツアーについて1行ごとに情報が与えられる。
Biはi番目の国のツアーに行った場合の満足度。
Ciはi番目の国のツアーに行かなかった場合の満足度。
Bi、Ciは共に0以上の整数。0≤Bi,Ci≤100。
必ずしもBi>Ciでないことに注意。
Mは0以上の整数。0≤M≤N×(N−1)2。
以下、M個のツアー参加の条件について1行ごとに情報が与えられる。
j番目の条件として、もしDj番目の国にもEj番目の国にも旅行するのであれば、
Dj番目の国のツアーに行ったらEj番目の国のツアーにも行かなければならない。
Dj、Ejは0以上N−1以下の整数。0≤Dj,Ej≤N−1。
このとき必ずDj<Ej。
i≠jであれば(Di,Ei)≠(Dj,EJ)

出力

最大の満足度を1行で答えよ。
改行を忘れずに。

サンプル

サンプル1
入力
2
20 10
30 50
1
0 1
出力
60

2つの国がある。
まず旅行に行く国を0番目と1番目の国に決める。
各国のツアーの満足度の情報は以下のようになる。
0番目の国のツアーに行くと満足度が20である。
0番目の国のツアーに行かないと満足度が10である。
1番目の国のツアーに行くと満足度が30である。
1番目の国のツアーに行かないと満足度が50である。
ツアーは必ず小さい番目の国から順に訪れる必要がある。
旅行会社から1つのツアーに関する条件がある。
0番目の国のツアーに参加したら1番目の国のツアーにも参加しなければならない。

もし旅行会社の条件が無ければ、
0番目の国のツアーに参加し1番目の国のツアーに参加しないのが最善である。
このとき満足度は20+50=70で最大になる。
ただし実際は0番目のツアーに参加すると1番目のツアーにも参加しなければならない。
この場合、満足度は20+30=50である。
結局、0番目のツアーにも行かず1番目のツアーにも行かないのがいちばん良い。
満足度は10+50=60である。
よって、最大の満足度は60となる。

サンプル2
入力
2
20 30
40 20
1
0 1
出力
70

まず旅行に行く国を0番目と1番目の国に決める。
次に、0番目の国のツアーに行かず1番目の国のツアーには行くと決める。
このとき最大の満足度は30+40=70である。
条件では0番目のツアーに行った時に1番目のツアーに行かなければならない。
ただし、逆に1番目のツアーに行くからといって0番目のツアーに行かないといけないわけではない。

サンプル3
入力
3
10 1
1 1
1 10
2
0 1
1 2
出力
20

まず旅行に行く国を0と2番目の国に決める。
0番目の国のツアーに行く。
2番目の国のツアーに行かない。
すると最大の満足度10+10=20が得られる。
もし1番目の国にも行くことを決めてしまうと、
0番目の国のツアーに行くときに1番目の国のツアーにも行かなければならない。
すると2番目の国のツアーにも行かなければならなくなってしまうので、
満足度は10+1+1=12と低くなってしまう。
必ずすべての国に行ったほうが有利でないことに注意。

サンプル4
入力
30
86 10
18 59
84 75
93 0
42 20
67 28
77 5
62 54
82 76
30 62
11 60
7 18
72 69
91 76
28 16
66 37
46 21
20 2
59 22
23 99
9 99
22 1
22 100
61 24
11 97
14 95
81 65
34 90
19 53
89 49
35
0 3
0 11
0 15
0 21
1 14
1 18
1 20
1 23
2 11
2 13
2 19
3 17
4 10
4 17
6 9
6 17
6 20
9 16
9 28
11 17
11 28
12 15
14 26
15 22
15 24
16 23
16 25
17 27
19 24
19 25
22 24
23 26
23 29
24 27
25 28
出力
1828

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。