#Psmt16. 2.序列破解

2.序列破解

2.序列破解

题目描述

有一个长度为N的序列,每个数字都是0或1。未知数按1到n编好了序。现可以通过支付一定代价询问第i个未知数到第j个未知数的和的奇偶性,给出每个区间[i,j]的询问代价,请找到一个方案,解出所有的未知数的值,并使代价的总和最小。

输入格式

第一行一个整数n;

第i+1行有n+1-i个整数,表示每一种询问所需的花费。

其中第i+1行第j+1-i个数c[i,j]表示对区间[i,j]进行询问的费用,

输出格式

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

数据范围

(原站未提供,导入后需人工补齐)

样例

3
1 2 3
2 2
1
4

提示

对于20%的数据,n<=4;

对于40%的数据,n<=8;

对于60%的数据,n<=13;

对于100%的数据,n<=2000。