← 返回题目列表

AtCoder · joi2009ho_c

C. 阿弥陀寺

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

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

あみだくじ - 原题 PDF 第 1 页
原题PDF第7页
あみだくじ - 原题 PDF 第 2 页
原题PDF第8页
あみだくじ - 原题 PDF 第 3 页
原题PDF第9页
可复制的 PDF 提取文本
3                   あみだくじ 


問題
 あなたはJ 君と一緒にあみだくじを使って遊んでいる.あみだくじはn 本の縦棒と
m 本の横棒からなる.縦棒には左から順に1 からn の番号がついており,縦棒i の下
端には正整数si が書かれている.

                            1    2    3    4





                           20   80   100   50
   図3-1 あみだくじの例(n = 4, m = 5, s1 = 20, s2 = 80, s3 = 100, s4 = 50)

 縦棒i の一番上から順に道をたどっていき到達した下端に書かれている整数が,縦
棒i を選んだ場合の得点である.例えば,図3-1 では,縦棒1 を選ぶと得点は80 点
であり,縦棒2 を選ぶと得点は100 点である.

             1    2    3    4            1    2    3    4





             20   80   100   50           20   80   100   50
                    図3-2 道のたどり方の例

                       問題3-1

J 君は縦棒1 から縦棒k までの連続したk 本を選ぶことにした.それらk 本の縦棒
を選んだときの点数の合計がJ 君の得点となる.ただし,あなたはあみだくじ内の
横棒を一本選び,その横棒をあみだくじから削除することができる.(削除しなくて
もよい.)もし,あなたが横棒を一本削除した場合は,削除後のあみだくじにおいて,
縦棒1 から縦棒k までの連続したk 本の縦棒を選んだときの点数の合計がJ 君の得点
となる.
 入力としてあみだくじの形とJ 君の選ぶ縦棒の本数k が与えられたとき,J 君の得
点の最小値を求めるプログラムを作成せよ.


入力

 入力ファイルのファイル名はinput.txt である.
  1 行目には4 つの整数n, m, h, k が空白区切りで書かれている.n (2 ≦n ≦1000) は
縦棒の本数を,m (1 ≦m ≦100000) は横棒の本数を,h (2 ≦h ≦1000) は縦棒の長
さを,k (1 ≦k ≦n) はJ 君が選ぶ縦棒の本数を表す.
 続くn 行には縦棒の下端に書かれている点数が書かれている.i+1 行目(1 ≦i ≦n)
には正整数si が書かれている.また,s1 + s2 + · · · + sn ≦2000000000 = 2 × 109 を満
たす.
 続くm 行には横棒の位置が書かれている.横棒には1 からm までの番号がつい
ている.i + n + 1 行目(1 ≦i ≦m) には,横棒i の位置を表す2 つの整数ai, bi
(1 ≦ai ≦n −1, 1 ≦bi ≦h −1) が空白区切りで書かれており,横棒i が縦棒ai と縦
棒ai + 1 を結び,横棒i の上端からの距離がbi であることを表す.ただし,どの2
つの横棒も端点を共有することはない.

 採点用データのうち,配点の20 % 分は横棒を削除しない場合にJ 君の得点が最少
となる.また,配点の30 % 分はn ≦20, m ≦30, h ≦10 を満たし,配点の60 % 分
はm ≦1000 を満たす.


出力

 出力ファイルのファイル名はoutput.txt である.
  output.txt はJ 君の得点の最小値のみを含む1 行からなる.





                       問題3-2

入出力の例
  例1               例2
   input.txt                   input.txt

       4 5 7 2                     2 2 5 1
       20                          10
       80                          20
       100                         1 1
       50                          1 3
       1 1
       2 6
                              output.txt
       2 3
       1 5                                   10
       3 1



   output.txt

       100


 例1 は図3-1 に対応し,あなたが横棒4 (縦棒1 と縦棒2 を上端から距離5 の場
所で結ぶ横棒)を削除したとき,J 君の得点は最小になる.例2 では,あなたが横棒
を削除しない場合にJ 君の得点が最小になる.(図3-3 を見よ.)

              1    2    3    4                     1    2





                                                    10   20


             20   80   100   50
                          図3-3



                       問題3-3