题目描述

小明和朋友们在航空博物馆玩捉迷藏，现在有N间房间连成一排，编号为1,2,…,N，其中某些房间里面有1个人（且不会超过1个），其它房间没有人。小明可以使用Cij个航天纪念币让博物馆管理员告诉他i,i+1,…,j这些房子里人员总数的奇偶性。采取最优的询问策略，小明至少需要使用多少纪念币，才能准确找到哪些房子里有人（能够处理人员任意分布的情形）？

输入说明

第一行是一个整数N(1≤N≤2000)。 接下来N行，第i行有（N-i+1）个数，代表Cij≤10^9，1≤i≤j≤N。

输出说明

输出一个整数，表示最少使用的纪念币个数。

输入样例 

5

1 2 3 4 5

4 3 2 1

3 4 5

2 1

5

输出样例

7

确定每个房间是否有人等价于确定所有的前缀的奇偶性。

如果知道   ( i-1 , i ],    的奇偶性，  即知道前缀i-1和前缀i 的关系：

1. 奇偶相同，i 没有人。

2. 奇偶不同，i有人。

我们需要知道  ( 0 , 1 ], ( 1 , 2 ],  ( 2 , 3 ], ......  ( N-1 , N ] 的奇偶性，实际上是要连通

0，1，2，3，......, N-1, N  这N+1个点。

对于区间 [ L , r ] 实际上就是连通了前缀L− 1 和前缀r。

所以我们的目的是： 选择N个最小费用的区间[ L , r ]，连通

0，1，2，3，......, N-1, N  这N+1个点。即求一个最小生成树，用kruskal算法