2017-2018 ACM-ICPC, Asia Tsukuba Regional Contest E：Black or White

这道题可以比较容易看出是线性DP。设dp[i]代表把前i个格子刷成目标状态的最小步数。

写出状态转移方程 dp[i]=min( dp[j]+calc(j+1,i) ) (i-j<=k) calc(j+1,i)代表把区间 [j+1,i] 的块刷成目标状态的最小代价。

那么问题在于怎么算calc(j+1,i)。这里直接给出结论:calc=(s[i]-s[j])/2+1，意思是最小代价是先把区间[j+1,i]刷成段数比较多的那种颜色，然后再一段一段把段数较小的刷好。代价就是1+(s[i]-s[j])/2。

把方程拆开  2*f[i]=2*f[j]+s[i]-s[j]+2     f[i]=(s[i]+(2*f[j]-s[j])+2) / 2  

观察式子发现只有  2*f[j]-s[j] 跟j相关，并且j的取值上下界都在变化。容易想到用单调队列优化。

这里还要主要一个小细节：例如 BBBWWW  那么s的值就是 111222  。此时s[5]-s[2]=1，事实上[3,4,5]这一段应该是两段组成，s[5]-s[2]应该等于2 。

所以要加入  if (s[i]==s[i+1]) s[i]--;   这一句代码。意思是i点还不是该段结尾点，i+1及后面还会有这一段的残余，然后令s[i]-1使得后面的s[p]减去s[i]的时候会算上这一段残余段（比较难表达，但就是这个意思qwq）。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,k,f[N],s[N],q[N];
char A[N],B[N];

int calc(int j) { return 2*f[j]-s[j]; }

int main()
{
    cin>>n>>k;
    scanf("%s",A+1); scanf("%s",B+1);
    for (int i=1;i<=n;i++) if (B[i]!=B[i-1]) s[i]=1;
    for (int i=1;i<=n;i++) s[i]+=s[i-1];
    
    int h=1,t=1; q[1]=0;
    for (int i=1;i<=n;i++) {
        while (h<=t && i-q[h]>k) h++;
        if (h<=t) f[i]=(s[i]+calc(q[h])+2)/2;
        if (A[i]==B[i]) f[i]=f[i-1];
        if (s[i]==s[i+1]) s[i]--;  //这一句很重要 
        while (h<=t && calc(i)<=calc(q[t])) t--;
        q[++t]=i;
    }    
    cout<<f[n]<<endl;
    return 0;
}