No.913 木の燃やし方

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 :

ei1333333 / テスター :

treeone

4 ProblemId : 3421 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2019-10-18 13:25:32

$N$ 本の木が横一列に植えられていて, 左から $i$ 番目の木の価値は $A_{i}$ です。

これから好きな連続する区間を選んで, 区間内にある木を全て燃やします。ここで, 悲しさを燃やした木の本数を $x$ として $x^{2} +$ (燃やした木の価値の総和) と定義します。

それぞれの木について, その木を必ず燃やす場合の悲しさの最小値を求めてください。

 $N$ 
 $A_{1}$   $A_{2}$   $\dots$   $A_{N}$

出力は $N$ 行からなります。 $i$ 行目には左から $i$ 番目の木を必ず燃やす場合の悲しさの最小値を出力してください。

3
-2 -5 100

-3
-4
99

木 $1$ を必ず燃やす場合, 木 $[1, 2]$ を燃やすのが最適でこのときの悲しさは $2^{2} + (- 2 - 5) = - 3$ です。
木 $2$ を必ず燃やす場合, 木 $[2, 2]$ を燃やすのが最適でこのときの悲しさは $1^{2} + (- 5) = - 4$ です。
木 $3$ を必ず燃やす場合, 木 $[2, 3]$ を燃やすのが最適でこのときの悲しさは $2^{2} + (- 5 + 100) = 99$ です。

5
-10000 0 -10000 0 -10000

どの木を必ず燃やす場合でも, すべての木を燃やすのが最適です。

1
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。