Cowreography

题目描述

奶牛们组建了一支舞蹈队，而农夫 John 是她们的编舞！这支队伍最新、最棒的舞蹈包含 $N$ 头奶牛（$2 \le N \le 10^6$）站成一排。 舞蹈中的每一步动作涉及两头奶牛：它们相距至多 $K$ 个位置（$1 \le K < N$），优雅地起跳并落到对方的位置上。 队列中有两种奶牛——根西牛（Guernsey）和荷斯坦牛（Holstein）。因此，农夫 John 将这段舞蹈记录为一个由长度为 $N$ 的二进制字符串组成的序列，其中 $0$ 表示根西牛，$1$ 表示荷斯坦牛，而整个字符串表示奶牛在队列中的排列方式。 不幸的是，农夫 Nhoj（为对手队伍编舞）破坏了这段舞蹈，把除第一和最后一个二进制字符串以外的记录全部擦掉了！眼看大型比赛迫在眉睫，农夫 John 必须争分夺秒地重建这段舞蹈。 给定这两个二进制字符串，帮助农夫 John 求出这段舞蹈所需的最少动作次数！

输入格式

第一行包含 $N$ 和 $K$。 第二行包含第一个二进制字符串。 第三行包含最后一个二进制字符串。 保证两个二进制字符串中 $1$ 的数量相同。

输出格式

输出这段舞蹈的最少动作次数。

4 1
0111
1110

3

5 2
11000
00011

3

5 4
11000
00011

2

提示

一种可能的舞蹈： 0111 -> 1011 -> 1101 -> 1110 一种可能的舞蹈： 11000 -> 01100 -> 00110 -> 00011 一种可能的舞蹈： 11000 -> 10010 -> 00011 评分（SCORING）： 输入 4-5：$K=1$ 输入 6-7：两个字符串中的 $1$ 的数量均不超过 $8$。 输入 8-15：$N\le 5000$ 输入 16-23：无额外限制。 题目来源：Benjamin Qi

标签: USACO|2024|Gold

来源

USACO|2024|Gold