#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。