Codeforces Round #642 (Div. 3) K-periodic Garland DP

给你一个01串，一次操作可以把0改成1，把1改成0。要求最少的改变次数，使这个01的1是间隔k出现。

思路：

#include<bits/stdc++.h>
#define LL long long
using namespace std;

char s[1000005];
int f[1000005][2], sum[1000005];
int main(){
    int t; scanf("%d", &t);
    while(t--){
        int n, k, ans=0;
        scanf("%d%d", &n, &k);
        scanf("%s", s+1);
        for(int i=1; i<=n; i++){
            if(s[i]=='1'){
                sum[i]=sum[i-1]+1;
                f[i][1]=min(sum[i-1],f[max(0, i-k)][1]+sum[i-1]-sum[max(0, i-k)]);
                f[i][0]=min(f[max(0, i-k)][1],f[max(0, i-k)][0])+sum[i-1]-sum[max(0, i-k)]+1;
            }
            else{
                sum[i]=sum[i-1];
                f[i][1]=f[max(0, i-k)][1]+sum[i-1]-sum[max(0, i-k)]+1;
                f[i][0]=min(f[max(0, i-k)][1],f[max(0, i-k)][0])+sum[i-1]-sum[max(0, i-k)];
            }
        }
        int Mi=1e7;
        for(int i=n; i>=n-k+1; i--){
            Mi=min(Mi, min(f[i][1], f[i][0])+sum[n]-sum[i]);
        }
        printf("%d\n", Mi);
    }

    return 0;
}