A - 区間分割の仕方を最適化する問題
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 100 点
問題文
N 個の要素が一列に並んでいます。これらの要素をいくつかの区間に分割したいとします。各区間 [l, r) には、スコア c_{l, r} が付いているものとします。
K を N 以下の正の整数として、K + 1 個の整数 t_0, t_1, \dots, t_K を、0 = t_0 \lt t_1 \lt \dots \lt t_K = N を満たすようにとり、N 個の要素を K 個の区間 [t_0, t_1), [t_1, t_2), \dots, [t_{K-1}, t_K) に分割します。このとき、この区間分割のスコアを次のように定めます。
- c_{t_0, t_1} + c_{t_1, t_2} + \dots + c_{t_{K-1}, t_K}
区間分割の仕方をすべて考えたときの、考えられるスコアの最小値を求めてください。なお、区間の個数 K についても自由に選択できるものとします。
入力
入力は次の形式で与えられます。
N c_{0,0} c_{0,1} \dots c_{0,N} c_{1,0} c_{1,1} \dots c_{1,N} \vdots c_{N,0} c_{N,1} \dots c_{N,N}
出力
最小スコアを出力してください。
制約
- 1 \le N \le 1{,}000
- 0 \le c_{l,r} \le 100
- c_{i, i} = 0
- c_{i, j} = c_{j, i}
-
入力はすべて整数
入力例
3 0 7 1 6 7 0 5 3 1 5 0 4 6 3 4 0
出力例
5
3 つの要素を、「最初の 2 個」と「最後の 1 個」の 2 つの区間に分割するのが最適です。このときのスコアは
- 最初の 2 個の要素からなる区間:1
- 最後の 1 個の要素からなる区間:4
を合計したものであり、1 + 4 = 5 です。