A4795 | 千纸鹤
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
小特同学正在给Doctor做卡兹戴尔特有的白色千纸鹤，捣蛋的益达干员悄悄地把其中一部分的千纸鹤染色成了黑色。
千纸鹤一共有$n$个，并且按照从左往右进行排列，其中第$i$个的千纸鹤颜色为$c_i$。若$c_i$为
小特同学可以施展魔法，每一次魔法需要选取任意连续的$k$个千纸鹤，并且使其变为白色。请问小特同学最少需要进行几次这样的操作呢？
千纸鹤一共有$n$个，并且按照从左往右进行排列，其中第$i$个的千纸鹤颜色为$c_i$。若$c_i$为
0，则代表为白色，若$c_i$为1，则代表为黑色。小特同学可以施展魔法，每一次魔法需要选取任意连续的$k$个千纸鹤，并且使其变为白色。请问小特同学最少需要进行几次这样的操作呢？
输入格式
第一行输入两个正整数$n,k$，代表千纸鹤数量和操作数量。
第二行输入$n$个整数$c_i$，代表每个千纸鹤的颜色，每两个数字用空格分开。
第二行输入$n$个整数$c_i$，代表每个千纸鹤的颜色，每两个数字用空格分开。
输出格式
输出一个整数,代表最小的操作次数。
输入输出样例
输入 #1
4 2 0 1 0 1
输出 #1
2
输入 #2
5 1 1 1 1 1 1
输出 #2
5
样例解释
在第一个测试用例中，您可以执行以下操作：
$$ \color{red}{\texttt{0}}\texttt{ 1 0 1} \to \texttt{0 0 0 1}\color{red}{\texttt{}} \to \texttt{0 0 0 0} $$
在第二个测试用例中，您可以执行以下操作：
$$ \texttt{}\color{red}{\texttt{1 1 1 1 1}}\texttt{} \to \texttt{0 1 1 1 1} \to \texttt{0 0 1 1 1} \to \texttt{0 0 0 1 1}\to \texttt{0 0 0 0 1}\to \texttt{0 0 0 0 0} $$
数据约束
对于30%的数据，满足 $1 \leq n \leq 100 , 1 \leq k \leq n$。
对于100%的数据，满足 $1 \leq n \leq 2 \times 10^5 , 1 \leq k \leq n$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？