A - 区間分割の仕方を最適化する問題 Editorial /

Time Limit: 2 sec / Memory Limit: 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 です。