#P18904. [2026多校联测]light

[2026多校联测]light

题目描述

一条灯带上有 nn 盏灯,从左到右编号 11 到 nn。每盏灯的状态用 00 或 11 表示,00 表示灭,11 表示亮。

一次操作可以选择一段长度恰好为 kk 的连续灯:选定 ll(1≤l≤n−k+11\le l\le n-k+1),把第 ll 盏到第 l+k−1l+k-1 盏灯的状态全部取反(00 变成 11,11 变成 00)。

求把所有灯都变成灭所需的最少操作次数。如果无法做到,输出 −1-1。

输入格式

第一行两个整数 n,kn,k。

第二行 nn 个整数,依次表示第 11 盏到第 nn 盏灯的状态,每个数为 00 或 11。

输出格式

一行一个整数,表示最少操作次数;如果无法做到,输出 −1-1。

样例 1

3 3
1 1 1
1

样例 2

6 3
1 1 0 1 1 0
2

样例 3

5 2
1 0 1 0 1
-1

样例解释

  • 样例 1:翻转第 1∼31\sim3 盏灯,11 次即可。
  • 样例 2:先翻转第 1∼31\sim3 盏灯,再翻转第 3∼53\sim5 盏灯,22 次即可;11 次不够。
  • 样例 3:每次操作翻转 22 盏灯,亮灯数量的奇偶性不变。初始有 33 盏灯亮(奇数),无法变成 00 盏灯亮。

子任务

测试点编号 约束 分值
1 n≤20n\le20 10
2-3 k=1k=1 20
4-5 k=nk=n 15
6-7 n≤3000n\le3000
8-10 无特殊限制 40

对于 100%100\% 的数据,1≤k≤n≤2×1051\le k\le n\le2\times10^5。