luogu#P9495. 「SFCOI-3」进行一个魔的除 I
「SFCOI-3」进行一个魔的除 I
题目背景
终于,勇士打败了魔王,他把走投无路的魔王困在了一个房间里。
魔王拥有在黑暗中随意穿行的能力,所以勇士只有把房间里所有的灯全部打开,才能找到魔王,最终彻底消灭他。
题目描述
房间中共有 盏灯,初始状态可以用 表示,其中 表示这盏灯初始是关闭的, 表示这盏灯初始是打开的。
从第一天早晨开始,魔王与勇士轮流行动:
- 每天早晨,魔王可以选择 连续的 两盏灯,将它们的状态全部设定为 ;
- 每天晚上,勇士可以选择 任意的 至多三盏灯,将它们的状态全部设定为 。
每次行动时选择的灯在设定前的状态任意。
假设双方均采用最优策略,不会进行任何不利于自己的行动。勇士想知道,最少 需要多少天(也即,他最少需要多少次操作)才能将所有灯状态设定为 ——这样,他才能抓到可恶的魔王,迎娶美丽的公主。
输入格式
第一行一个整数 ,表示数据组数。
对于每组数据:
- 第一行一个整数 ,表示灯的总数。
- 第二行共 个数,依次表示 。
输出格式
对于每组数据,一行一个整数,代表勇士抓到魔王所需要的最少天数。
特别地,如果勇士不需要任何操作,输出 即可。
4
5
1 0 1 0 1
5
1 0 0 1 1
9
0 0 0 0 0 0 0 0 0
13
0 1 0 0 1 0 1 0 0 0 0 0 0
1
2
5
8
提示
样例解释 1
- 第一天早晨,魔王关闭第 两盏灯;
- 第一天晚上,勇士打开 三盏灯。
样例解释 2
- 第一天早晨,魔王关闭第 两盏灯;
- 第一天晚上,勇士打开 三盏灯。
- 第二天早晨,魔王关闭第 两盏灯;
- 第二天晚上,勇士打开 三盏灯。
数据规模与约定
本题采用捆绑测试。
- Subtask 0(10 points):,。
- Subtask 1(30 points):。
- Subtask 2(10 points):初始所有灯都是关闭的。
- Subtask 3(20 points):数据随机生成。
- Subtask 4(30 points):无特殊限制。
对于所有数据,,,。