#PU1425. USACO 2024 US Open Contest, Gold — Problem 1. Cowreography

    ID: 1663 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:open24来源:usaco.orgscoring:equal_test_cases线段树动态规划

USACO 2024 US Open Contest, Gold — Problem 1. Cowreography

USACO 2024 US Open Contest, Gold — Problem 1. Cowreography

题目描述

The cows have formed a dance team, and Farmer John is their choreographer! The team's latest and greatest dance involves NN cows (2≤N≤1062 \le N \le 10^6) standing in a line. Each move in the dance involves two cows, up to KK positions apart (1≤K<N1 \le K < N), gracefully jumping and landing in each other's position. There are two types of cows in the line – Guernseys and Holsteins. As such, Farmer John has documented the dance as a sequence of length-NN binary strings , where a 00 represents a Guernsey, a 11 represents a Holstein, and the overall string represents how the cows are arranged in the line. Unfortunately, Farmer Nhoj (who choreographs for a rival team) has sabotaged the dance and erased all but the first and last binary strings! With a big competition quickly approaching, Farmer John must waste no time in reconstructing the dance. Given these two binary strings, help Farmer John find the minimum number of moves in the dance!

输入格式

The first line contains NN and KK. The second line contains the first binary string. The third line contains the last binary string. It is guaranteed that both binary strings contain the same number of ones.

输出格式

The minimum number of moves in the dance.

数据范围

Inputs 4-5: K=1K=1 Inputs 6-7: Both strings have at most 88 ones. Inputs 8-15: N≤5000N\le 5000 Inputs 16-23: No additional constraints. Problem credits: Benjamin Qi

样例

样例 1

4 1
0111
1110
3
One possible dance:
0111 -> 1011 -> 1101 -> 1110

样例 2

5 2
11000
00011
3
One possible dance:
11000 -> 01100 -> 00110 -> 00011

样例 3

5 4
11000
00011
2
One possible dance:
11000 -> 10010 -> 00011