Problem I: 玩捉迷藏
| Time Limit |
$2$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$2$ |
正确数量 |
$2$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
|
当前分类(单击移除)：
单击选择分类：
小明和朋友们在航空博物馆玩捉迷藏，现在有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