Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!