链接：https://vjudge.net/contest/399019#problem/B
You are given a garland consisting of nn lamps. States of the lamps are represented by the string ss of length nn. The ii-th character of the string sisi equals '0' if the ii-th lamp is turned off or '1' if the ii-th lamp is turned on. You are also given a positive integer kk.
In one move, you can choose one lamp and change its state (i.e. turn it on if it is turned off and vice versa).
The garland is called kk-periodic if the distance between each pair of adjacent turned on lamps is exactly kk. Consider the case k=3k=3. Then garlands "00010010", "1001001", "00010" and "0" are good but garlands "00101001", "1000001" and "01001100" are not. Note that the garland is not cyclic, i.e. the first turned on lamp is not going after the last turned on lamp and vice versa.
Your task is to find the minimum number of moves you need to make to obtain kk-periodic garland from the given one.
You have to answer tt independent test cases.
Input
The first line of the input contains one integer tt (1≤t≤25 0001≤t≤25 000) — the number of test cases. Then tt test cases follow.
The first line of the test case contains two integers nn and kk (1≤n≤106;1≤k≤n1≤n≤106;1≤k≤n) — the length of ss and the required period. The second line of the test case contains the string ss consisting of nn characters '0' and '1'.
It is guaranteed that the sum of nn over all test cases does not exceed 106106 (∑n≤106∑n≤106).
Output
For each test case, print the answer — the minimum number of moves you need to make to obtain kk-periodic garland from the given one.
Example
Input
6 9 2 010001010 9 3 111100000 7 4 1111111 10 3 1001110101 1 1 1 1 1 0
Output
1 2 5 4 0 0
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=1e6+7;
const ll mod=1e9+7;
ll t,n,k,s,ans;
char x[maxn];
ll dp[maxn][2];
ll a[maxn];
int main()
{cin>>t;while(t--){cin>>n>>k;cin>>x;s=0;ans=mod;for(int i=0;i<n;i++){if(x[i]=='1')s++;dp[i][0]=0;dp[i][1]=0;a[i]=s;}if(x[0]=='1')dp[0][1]=0,dp[0][0]=1;elsedp[0][0]=0,dp[0][1]=1;ans=min(ans,dp[0][1]+a[n-1]-a[0]);ans=min(ans,dp[0][0]+a[n-1]-a[0]);for(int i=1;i<n;i++){if(x[i]=='1')dp[i][1]=0,dp[i][0]=1;elsedp[i][0]=0,dp[i][1]=1;dp[i][0]+=min(dp[i-1][0],dp[i-1][1]);if(i-k>=0){dp[i][1]+=min(dp[i-k][1]+a[i-1]-a[i-k],a[i-1]);}else{dp[i][1]+=a[i-1];}ans=min(ans,dp[i][1]+a[n-1]-a[i]);ans=min(ans,dp[i][0]+a[n-1]-a[i]);}cout<<ans<<endl;}return 0;
}