Round821 Div2 D2

题目描述

给定两个相同长度的01串。现在要对串1进行操作，选择两个位置，让它们0变成1，1变成0，如果是相邻位置，费用为，不相邻位置费用为。求最小费用使得两串一致。

解题思路

首先，不相同位置的个数必须是偶数才能操作。

当时，我们可以使用贪心算法，交换不相邻位置，答案为。

当时，我们使用动态规划来完成。我们记表示前位已经满足条件所需要的最小费用。

根据常见的动态规划考虑策略，我们需要枚举从哪个位置与当前位置发生的交换。交换的策略加上两者之间的答案再加上之前的答案就是整个的答案贡献。

因此我们可以做区间dp，但是复杂度是的，无法通过本题。

我们考虑如何计算两者之间贡献的答案。首先我们考虑这之中是否会有交换的发生。答案是不会。因为如果有交换的发生，假设与之间发生交换，那么我们完全可以换成与、与之间的交换。如果与之间发生的是相邻交换，那么我们完全可以将相邻交换的距离限制到到，让与发生交换，那么答案会更小。

接下来我们考虑是否这个区间的个数可能为奇数呢？答案也是不会。如果为奇数，其中必定有一个数字会与区间外的数字发生交换，这个数字小于。我们完全可以转换为与交换，与交换。如果它们中至少有一个相邻，那么答案的贡献应该是，这个答案会比当前答案小，并且在其它的情况中得到，因此这个答案完全可以被抛弃。倘若与之间发生的是相邻交换，那么和发生交换，与发生交换明显更为优秀。因此区间内也不可能出现奇数个数。

因此我们可以列出状态转移方程：