#P18904. [2026多校联测]light
[2026多校联测]light
题目描述
一条灯带上有 盏灯,从左到右编号 到 。每盏灯的状态用 或 表示, 表示灭, 表示亮。
一次操作可以选择一段长度恰好为 的连续灯:选定 (),把第 盏到第 盏灯的状态全部取反( 变成 , 变成 )。
求把所有灯都变成灭所需的最少操作次数。如果无法做到,输出 。
输入格式
第一行两个整数 。
第二行 个整数,依次表示第 盏到第 盏灯的状态,每个数为 或 。
输出格式
一行一个整数,表示最少操作次数;如果无法做到,输出 。
样例 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:翻转第 盏灯, 次即可。
- 样例 2:先翻转第 盏灯,再翻转第 盏灯, 次即可; 次不够。
- 样例 3:每次操作翻转 盏灯,亮灯数量的奇偶性不变。初始有 盏灯亮(奇数),无法变成 盏灯亮。
子任务
| 测试点编号 | 约束 | 分值 |
|---|---|---|
| 1 | 10 | |
| 2-3 | 20 | |
| 4-5 | 15 | |
| 6-7 | ||
| 8-10 | 无特殊限制 | 40 |
对于 的数据,。