Skip to content

14167: 【原4167】猜小球

题目

题目描述

author: Mole 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4167

题目描述

苏前端跟侯不会在玩一个游戏,苏前端有\(n\)个不透明的杯子,每个杯子下可能扣着一个小球,也可能没有(注意有小球的情况只会有一个小球)。现在苏前端把这些杯子在桌子上一字排开,侯不会的目的是准确的得出每个杯子下有没有小球。侯不会每次可以询问苏前端第\(i\)到第\(j\)个杯子下所有小球总数的奇偶情况。当然,理财大师苏前端会需要你支付一个他给定的\(W_{ij}\)的代价。同为理财大师的侯不会想要用最小的代价求出每个杯子下有没有小球。侯不会自己当然是会的,但是他想要锻炼你的能力,希望你能帮他求出这个最小的代价。

输入格式

输入共\(n + 1\)行
第1行一个整数\(n\),表示桌上有\(n\)个小球
接下来\(n\)行,第\(i\)行包含\(i-1\)个整数,第\(i+1\)行的第\(j\)个数表示\(W_{ij}\)

输出格式

输出共一个整数,表示最少代价

样例输入

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_{ij} \leq 10^6\)

Oops! 本题目还没有解答!

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

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

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