No.119 旅行のツアーの問題
nmnmnmnmnmnmnm問題文
N個の国があります。
国は０番目からN-1番目と数えます。
A君はN個の国から旅行に行きたい国を選びました。
A君は必ず小さい番目の国から順に旅行に出かけます。
旅行会社に行くと各国にはそれぞれ１つのツアーがあるようでした。
ただし、旅行会社のツアーというものは良いものもあれば、
返って自由度が減って嫌なものもあります。
ツアーに行くか行かないかで満足度が設定されています。
また、旅行会社の人が言うには、あるツアーに行ったら別の国のツアーにも参加しないといけない。
という条件がいくつかあるようでした。
例えば、
・x番目の国のツアーに行ったらy番目の国のツアーに行かなければならない(x<y)
というような条件です。
もし、x番目の国とy番目の国の両方に行くならこの条件が発生します。
A君は理由はよくわからないけど条件を呑むことにしました。
旅行の全行程を通して満足度は加算されていきます。
A君はより多くの満足度を得たいです。
最大の満足度を答えなさい。
すなわち、それぞれ条件をみたすのなら、
・x番目の国に行かない。
・x番目の国に行くけど、ツアーには参加しない。
・x番目の国に行き、ツアーにも参加する。
のどれかの選択ができるということである。
入力
$N$
$B_0$ $C_0$
$\vdots$
$B_{n-1}$ $C_{n-1}$
$M$
$D_0$ $E_0$
$\vdots$
$D_{m-1}$ $E_{m-1}$
$N$は正の整数。$1 \le N \le 40$。
以下、$N$個の国のツアーについて1行ごとに情報が与えられる。
$B_i$は$i$番目の国のツアーに行った場合の満足度。
$C_i$は$i$番目の国のツアーに行かなかった場合の満足度。
$B_i$、$C_i$は共に$0$以上の整数。$0 \le B_i,C_i \le 100$。
必ずしも$B_i > C_i$でないことに注意。
$M$は$0$以上の整数。$0 \le M \le \frac{N\times(N-1)}{2}$。
以下、$M$個のツアー参加の条件について1行ごとに情報が与えられる。
$j$番目の条件として、もし$D_j$番目の国にも$E_j$番目の国にも旅行するのであれば、
$D_j$番目の国のツアーに行ったら$E_j$番目の国のツアーにも行かなければならない。
$D_j$、$E_j$は$0$以上$N-1$以下の整数。$0 \le D_j,E_j \le N-1$。
このとき必ず$D_j < E_j$。
$i \neq j $であれば$(D_i,E_i) \neq (D_j,E_J)$
出力
最大の満足度を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もしくは右上の雲マークをクリックしてアカウントを作成してください。