← 返回题目列表

AtCoder · joisc2008_nile

nile. 尼罗河网

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

ナイルドットコム (Nile.Com) - 原题 PDF 第 1 页
原题PDF第1页
ナイルドットコム (Nile.Com) - 原题 PDF 第 2 页
原题PDF第2页
可复制的 PDF 提取文本
Nile.Com: ナイルドットコム


input ファイル“nile.in”
output 標準出力
ソースファイルnile.c/nile.cpp
時間制限1 秒/ データ


 あなたの配偶者はD 日間毎日インターネットで一種類の商品を購入する.彼女(彼)が使っ

ているナイルドットコムのマーケットプレイスにはN 店舗が出店している.彼女は毎日そのう

ちの1 店舗を選んでショッピングをする.各店舗の価格は毎日変化するので予定価格が提示さ

れている.また,このマーケットプレイスでは同じ店舗で2 日続けて購入すると1 割引に,3 日

続けて購入すると3 割引になる.ただし,それ以降は何日続けて購入しても3 割引である.

 節約家の彼女のために予定価格を基にショッピングの計画を作成することにした.D 日間に

支払う合計金額が最小になるように買い物したときの合計金額を求めよ.

 ただし,ナイルドットコムのマーケットプレイスの店舗には識別のため1 からN までの店舗

番号が付けられていて,各店舗の予定価格は10 の倍数である.


Input. 入力ファイルnile.in は(D+1) 行のファイルであり,最初の行には店舗数N とショッ

ピングをする日数D が空白で区切って書かれている.ただし,2 ≦N ≦3, 000, 2 ≦D ≦365

である.

 続くD 行にはそれぞれN 個の10 以上100, 000 以下の10 の倍数が書かれている.これらの

数は金額を表わしていて各行に,1 日分ずつ日を追って,店舗番号の順に各店舗の割引き前の予

定価格が書かれている.つまり, 1 ≦d ≦D, 1 ≦n ≦N のとき, (d + 1) 行目のn 番目の数は第

d 日に店舗番号n の店舗の金額で割引き無しで購入した場合の予定価格である.


Output. 出力は,標準出力に行うこと.出力は1 行からなる.最小の合計金額を出力せよ.

採点基準採点用データのうち, 配点の40% 分については,N ≦200 であり,全データの20%

分についてはN ≦10, D ≦10 である.


例1
 nile.in   標準出力
 4 5          152
 50 30 80 70
 50 30 50 40
 50 50 60 50
 30 90 40 50
 70 30 70 80

                   ナイルドットコム–1/2

この例では, 第1日から順に店舗番号2 2 2 1 2 と選ぶのが30+0.9·30+0.7·50+30+30 = 152

で最小である.

例2
 nile.in     標準出力
 4 5              481
 110 160 80 200
 150 170 80 120
 80 150 160 160
 160 110 200 110
 150 190 160 190

 この例では, 第1 日から順に店舗番号3 3 1 1 1 と選ぶのが80 + 0.9 · 80 + 80 + 0.9 · 160 +

0.7 · 150 = 481 で最小である.





                   ナイルドットコム–2/2