题解 AT4514 【[AGC030E] Less than 3】

· · 题解

Solution

考虑在 0 与 1 间画一条红线，1 与 0 间画一条蓝线，并且假设开头和结尾都有无线交替的红蓝线，那么两个串相等等价于它们对应的红蓝线相等。每次可以移动一条红线或蓝线，要保证移动后红蓝线交替出现且相邻的红蓝线距离为 1 或 2，具体如下图。

假设我们已经确定了s中的红线和t中的蓝线的对应关系，显然答案的下界是对应线段的距离之和，在下图中答案为

\cdots +0+0+0+1+0+1+2+3+2+1+0\cdots=10

这个下界也是能达到的，因为要求相邻线之间的距离不超过 2，所以向右移的线和向左移动的线不能相邻，那么就相当于保持不动的线将所有线分成了若干部分，每一部分的线都是向同一个方向移动，显然在每一部分内一定存在一种移动方案。

由于本质不同的安排对应线段的方案只有 \mathcal O(n) 种，所以可以枚举对应方案，计算答案即可，时间复杂度 \mathcal O(n^2)

Code

int n,tot1,tot2,ans = INF;
int a[MAXN],b[MAXN];
char s[MAXN],t[MAXN];

int main(){
    scanf("%d%s%s",&n,s + 1,t + 1);
    for(int i = 1;i < n;i++){
        if(s[i] != s[i + 1]) a[++tot1] = i;
    }
    for(int i = 1;i < n;i++){
        if(t[i] != t[i + 1]) b[++tot2] = i;
    }
    for(int i = -tot1 - 1;i <= tot2 + 1;i++){
        if((i & 1) ^ (s[1] == t[1])){
            int sum = 0;
            for(int j = min(1,1 - i);j <= max(tot1,tot2 - i);j++)
                sum += abs((j < 0 ? 0 : (j <= tot1 ? a[j] : n)) - (i + j < 0 ? 0 : (i + j <= tot2 ? b[i + j] : n)));
            ans = min(ans,sum);
        }
    }
    printf("%d\n",ans);
    return 0;
}