AT_atc002_c 最適二分探索木

[problemUrl]: https://atcoder.jp/contests/atc002/tasks/atc002_c $ n $ 個の葉を持つ順序付き二分木を作りたい。 この二分木のコストは以下のように定義される。 $ Σ_{i=1}^{n}\ w_i\ ×\ depth(i) $ ただし、$ depth(i) $ は、二分木における左から $ i $ 個目の葉の深さを表す。 $ w_i $ は入力として与えられる重みである。 コストの最小値を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ n $ $ w_1 $ $ w_2 $ ... $ w_n $ - $ 1 $ 行目には、要素の個数を表す整数 $ n\ (1≦n≦100,000) $ が与えられる。 - $ 2 $ 行目には、要素の重みを表す $ n $ 個の整数が与えられる。このうち $ i\ (1≦i≦n) $ 番目の要素は、$ i $ 番目の要素の重みを表す $ w_i(1≦w_i≦1,000) $ である。

条件を満たす順序付き二分木のコストの最小値を出力せよ。

### 部分点 この問題には部分点が設定されている。 - $ n\ ≦\ 100 $ を満たすデータセットに正解した場合は、$ 50 $ 点が与えられる。 - $ n\ ≦\ 3,000 $ を満たすデータセットに正解した場合は、上記とは別に $ 50 $ 点が与えられる。 - 追加の制約のないデータセットに正解した場合は、上記とは別に $ 1 $ 点が与えられる。 ### 解説 **[最適二分探索木問題](//www.slideshare.net/secret/N435vV6yFDRsmK "最適二分探索木問題")** from **[AtCoder Inc.](//www.slideshare.net/chokudai)** - - - - - - ### 入力例1 ``` 6 1 2 3 4 9 3 ``` ### 出力例1 ``` 53 ``` 以下の図のような二分木が最適となります。 図 1 : サンプル入出力に相当する二分木 このような二分木を作った場合、コストは 53 になります。