← 返回题目列表

AtCoder · joi2010ho_b

B. 分裂糖果

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

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

お菓子の分割 - 原题 PDF 第 1 页
原题PDF第5页
お菓子の分割 - 原题 PDF 第 2 页
原题PDF第6页
可复制的 PDF 提取文本
2                  お菓子の分割 


問題
 長さN ミリメートルの棒状のお菓子が1 本ある(ここでN は偶数).2 人のJOI
関係者が,このお菓子を複数本に切断して,合計N ミリメートルずつに分けること
                                           2
にした.
 理由は不明であるが,このお菓子は場所によって切断のしやすさが異なっている.
2 人は,お菓子を左から1 ミリメートルごとに調べ,各場所で切断に何秒かかるか
を割り出した.2 人がお菓子を分けるための切断にかかる秒数の最小値を求めるプ
ログラムを作成せよ.


入力

 入力ファイルのファイル名はinput.txt である.
 入力の1 行目には,棒の長さN(2 ≦N ≦10000 ,ただしN は偶数) が書かれてい
る.入力のi + 1 行目(1 ≦i ≦N −1) には,左端からi ミリメートル目の場所の切
断にかかる秒数を表す整数ti (1 ≦ti ≦10000) が書かれている.切断可能な場所が
N −1 箇所であることに注意せよ.
 採点用データのうち,配点の5% 分については,高々2 カ所を切断することで最
小値を実現でき,10% 分については,高々3 カ所を切断することで最小値を実現で
きる.配点の20% 分については,N ≦20 である.


出力

 出力ファイルのファイル名はoutput.txt である.
  2 人がお菓子を分るための切断にかかる秒数の最小値を含む1 行からなる.





                       問題2-1

入出力の例

input.txt

     6
     1
     8
     12
     6
     2

output.txt

     7

 この場合,左端から1 ミリメートルと4 ミリメートルの場所で切断するとかかる
秒数が最小となる.かかる秒数は1 秒と6 秒で,合計7 秒である.





                       問題2-2