← 返回题目列表

AtCoder · awc0086_e

E. 舞蹈同步

中文机器翻译题面 查看原题

分数: 433 分

问题陈述

高桥和青木各有一个由左右步组成的舞蹈编排。高桥的编舞以弦乐为代表 s,青木的编舞用字符串表示 t,其中每个字符是 0 (左步骤)或 1 (右步骤)。两种编排均不包含同一步骤的连续三次出现。

演出前排练时,高桥最多可以进行以下修改 K 次:

  • 选择一个位置 s or t,并将该步骤更改为相反的步骤。
  • 但是,更改后,该位置的步骤必须与同一编排中的所有相邻步骤不同。

排练后,高桥将一些舞步配对 s 和 t 创建“同步点”。配对必须满足以下所有条件:

  • 每对由一个位置组成 i in s 和一个位置 j in t.
  • 仅位置 s_i = t_j 可以配对。
  • 中的每个位置 s 和每个位置 t 最多可用于一对。
  • 配对不得相互交叉。也就是说,对于对 (i, j) 和 (i', j'),如果 i < i' 然后 j < j' 必须保留。

确定通过执行最佳修改和配对可以形成的最大配对数。

约束

  • 1 \leq |s| \leq 2 \times 10^5
  • 1 \leq |t| \leq 2 \times 10^5
  • |s| \times |t| \leq 2 \times 10^6
  • s 是一个仅包含以下内容的字符串 0 和 1.
  • t 是一个仅包含以下内容的字符串 0 和 1.
  • s 不包含同一字符连续出现三个或以上。
  • t 不包含同一字符连续出现三个或以上。
  • 0 \leq K \leq |s| + |t|
  • K 是一个整数。

输入

s
t
K
  • 第一行包含字符串 s 组成 0 和 1.
  • 第二行包含字符串 t 组成 0 和 1.
  • 第三行包含一个整数 K,表示可以进行的修改数量的上限。

输出

以整数形式输出可以组成的最大配对数。


示例输入 1

0101
0011
1

示例输出 1

3

示例输入 2

01
10
0

示例输出 2

1

示例输入 3

010110100110110010101101001011
1010010110100110101100101101
5

示例输出 3

24

示例输入 4

001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011001011
110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100110100
40

示例输出 4

100

示例输入 5

0
1
2

示例输出 5

1