J12 实践-1 猜球游戏

题目描述

魔术师的桌子上有 $n$个杯子排成一行，编号为 $1,2,…,n$，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。花费 $c_{i,j}$元，魔术师就会告诉你杯子 $i,i+1,…,j$ 底下藏有球的总数的奇偶性。 采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？

输入格式

第一行一个整数 $n$。 第 $i+1$行，有 $n+1-i$ 个整数，表示每一种询问所需的花费。其中$c_{i,j}$（对区间 [i,j] 进行询问的费用，$1\le i\le j\le n$）为第 $i+1$ 行第 $j+1-i$个数。

输出格式

输出一个整数，表示最少花费。

输入样例

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

输出样例

7

样例说明

如上所述。

数据范围

对于$100\%$的数据，保证 $1 \le n \le 2000,1 \le c_{i,j }\le 10^9$；