luogu#P9495. 「SFCOI-3」进行一个魔的除 I

    ID: 13466 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>贪心2023洛谷原创O2优化构造Ad-hoc

「SFCOI-3」进行一个魔的除 I

题目背景

终于,勇士打败了魔王,他把走投无路的魔王困在了一个房间里。

魔王拥有在黑暗中随意穿行的能力,所以勇士只有把房间里所有的灯全部打开,才能找到魔王,最终彻底消灭他。

题目描述

房间中共有 nn 盏灯,初始状态可以用 a1ana_1\dots a_n 表示,其中 0\tt 0 表示这盏灯初始是关闭的,1\tt 1 表示这盏灯初始是打开的。

从第一天早晨开始,魔王与勇士轮流行动:

  • 每天早晨,魔王可以选择 连续的 两盏灯,将它们的状态全部设定为 0\tt 0
  • 每天晚上,勇士可以选择 任意的 至多三盏灯,将它们的状态全部设定为 1\tt 1

每次行动时选择的灯在设定前的状态任意。

假设双方均采用最优策略,不会进行任何不利于自己的行动。勇士想知道,最少 需要多少天(也即,他最少需要多少次操作)才能将所有灯状态设定为 1\tt 1——这样,他才能抓到可恶的魔王,迎娶美丽的公主。

输入格式

第一行一个整数 TT,表示数据组数。

对于每组数据:

  • 第一行一个整数 nn,表示灯的总数。
  • 第二行共 nn 个数,依次表示 a1ana_1\dots a_n

输出格式

对于每组数据,一行一个整数,代表勇士抓到魔王所需要的最少天数。

特别地,如果勇士不需要任何操作,输出 00 即可。

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

  • 第一天早晨,魔王关闭第 1,21{,}2 两盏灯;
  • 第一天晚上,勇士打开 1,2,41{,}2{,}4 三盏灯。

样例解释 2

  • 第一天早晨,魔王关闭第 4,54{,}5 两盏灯;
  • 第一天晚上,勇士打开 2,3,42{,}3{,}4 三盏灯。
  • 第二天早晨,魔王关闭第 1,21{,}2 两盏灯;
  • 第二天晚上,勇士打开 1,2,51{,}2{,}5 三盏灯。

数据规模与约定

本题采用捆绑测试

  • Subtask 0(10 points):n10n \leq 10T2046T \leq 2046
  • Subtask 1(30 points):n2000 n \leq 2000
  • Subtask 2(10 points):初始所有灯都是关闭的。
  • Subtask 3(20 points):数据随机生成。
  • Subtask 4(30 points):无特殊限制。

对于所有数据,1T1061 \leq T \leq 10^61n1061 \leq n \leq 10^61n3×1061 \leq \sum n \leq 3 \times 10^6