[PA2014]Kuglarz
时间限制：20s 空间限制：128MB
题目描述
魔术师的桌子上有n个杯子排成一行，编号为1,2,…,n，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。花费c_ij元，魔术师就会告诉你杯子i,i+1,…,j底下藏有球的总数的奇偶性。
采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？
输入格式
第一行一个整数n(1<=n<=2000)。
第i+1行(1<=i<=n)有n+1-i个整数，表示每一种询问所需的花费。其中c_ij（对区间[i,j]进行询问的费用，1<=i<=j<=n,1<=c_ij<=10^9）为第i+1行第j+1-i个数。
输出格式
输出一个整数，表示最少花费。
样例输入
5 1 2 3 4 5 4 3 2 1 3 4 5 2 1 5
样例输出
7
提示
没有写明提示
题目来源
鸣谢Jcvb