概要
二種類の交通機関 A, B があり、それぞれいくつかの車両が走っている。
これらの交通機関で使えるチケットが四種類あり、i 番のチケットの価格は である。
チケットの詳細は次のようになる。
- A または B の一つの車両を一回利用できる
- A または B の一つの車両を何度でも利用できる
- A, B どちらかの全ての車両を何度でも利用できる
- A, B 両方の全ての車両を何度でも利用できる
それぞれの車両を利用したい回数が与えられる。
必要なチケット代の最小値を求めよ。
解法
一つの交通機関について考えます。
このとき、3 を一枚買うか、1 と 2 だけで利用するかの二通りが考えられます。
1 か 2 だけで利用する場合のチケット代は、一つの車両を利用する回数を とすると、 となります。
1, 2, 3 は全て一つの交通機関に関するもので、4 だけが二つに関わるので、購入パターンは次の二つです。
- それぞれの交通機関を 1, 2, 3 で利用する
- 4 を一枚買う。
それぞれの買い方を試して、最小値をとれば解けます。
コード
main = do [ [ c1, c2, c3, c4 ] , _, as, bs ] <- replicateM 4 $ do map read . words <$> getLine let f a = min ( c1 * a ) c2 print $ min c4 $ min c3 ( sum ( map f as ) ) + min c3 ( sum ( map f bs ) )