1043: 猜小球

$n$ 个不透明的杯子排成一排，每个杯子下面可能扣着一个小球，也可能没有。

你可以进行若干次以下询问，每次给定 $i,j(i<j)$，可以得到第 $i$ 个杯子到第 $j$ 个杯子下所有小球的总数，但是需要花费 $W_{i,j}$ 的代价。

如果你想要知道每一个杯子下面是否有小球，请计算需要的最小代价。

输入共 $n+1$ 行。

第一行一个整数 $n$。

接下来 $n$ 行，第 $i+1$ 行包含 $n-i+1$ 个整数，第 $i+1$ 行的第 $j$ 个数表示 $W_{i,i+j-1}$。

输出共一个整数表示最小代价。

5 1 2 3 4 5 4 3 2 1 3 4 5 2 1 5

7

对于30%的数据，$n\leq 100$

对于100%的数据，$n\leq 1000, W_{i,j}\leq 10^6$

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！