题意：给定只有黑白两种颜色的序列A,B，每次可以选择一段连续的长度不超过k的区间将其染成同一种颜色，求把序列A变成B所需的最小操作次数。

首先需要找出一些最优解的特征：

1.如果序列A的第一个颜色和B的相同，那么可以忽略掉。如果相反，那么必须将其染成相反的颜色。

2.最优解不会交叉，因为假如出现交叉的话，那么中间交叉的一段相当于做了无用功。

这样就可以进行dp了，将操作从左往右进行，假设前i-1个位置都已经染好了，如果A和B的第i位相同，那么忽略掉，如果相反，那么把它染成相反的颜色，然后只需要考虑右端延伸到哪里的问题。

自己手动模拟一下就会发现，假如B[l,r]一共有x段连续的颜色，那么最少需要$\left\lfloor \frac{x+2}{2}\right\rfloor$次操作就能将A[l,r]染成对应的颜色（在第一次操作将A[l,r]全部染成B[l]的前提下），由此可得递推式：$dp[i]=min\{dp[j]+\left\lfloor \frac{sum(j+1,i)+2}{2}\right\rfloor\},i-k\leqslant j<i$，dp[i]表示将前i个位置染好的最小操作次数。

如何快速求一段区间里的连续颜色段数量呢？区间连续颜色段数量相当于跨过了多少边界，而边界数可以用前缀和S来表示。对于每个位置，如果该位置和它前面位置的颜色不同，那么前缀和+1。这样，区间[l,r]上的连续颜色段数量就等于S[r]-S[l]+1（注意不是S[r]-S[l-1]+1，这里相当于把边权加到了点权上），于是递推式变成了：$\begin{aligned}dp[i]=&min\{dp[j]+\left\lfloor \frac{(S[i]-S[j+1]+1)+2}{2}\right\rfloor\}\\=&min\{dp[j]+\left\lfloor \frac{S[i]-S[j+1]+3}{2}\right\rfloor\}\\=&min\{\left\lfloor \frac{2dp[j]+S[i]-S[j+1]+3}{2}\right\rfloor\}\\=&\left\lfloor \frac{S[i]+min\{2dp[j]-S[j+1]\}+3}{2}\right\rfloor,i-k\leqslant j<i\end{aligned}$

这个递推式可以用滑动窗口+单调队列维护，复杂度$O(n)$

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=5e5+10,inf=0x3f3f3f3f;
 5 int n,k,S[N],dp[N],hd,tl;
 6 char a[N],b[N];
 7 struct D {int x,y;} q[N];
 8 int main() {
 9     scanf("%d%d%s%s",&n,&k,a+1,b+1);
10     for(int i=1; i<=n; ++i)S[i]=S[i-1]+(b[i]!=b[i-1]);
11     dp[0]=hd=tl=0;
12     q[tl++]= {0,-1};
13     for(int i=1; i<=n; ++i) {
14         for(; hd<tl&&i-q[hd].x>k; ++hd);
15         dp[i]=a[i]==b[i]?dp[i-1]:(S[i]+q[hd].y+3)/2;
16         D np= {i,2*dp[i]-S[i+1]};
17         for(; hd<tl&&q[tl-1].y>=np.y; --tl);
18         q[tl++]=np;
19     }
20     printf("%d\n",dp[n]);
21     return 0;
22 }