分数: 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