Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define readFile freopen("in.txt","r",stdin)
- #define writeFile freopen("out.txt","w",stdout)
- #define fastIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
- using namespace std;
- const int N = 100010;
- int dp[N], tree[4*N], alt[N];
- int n,k;
- string s;
- void update(int node, int l, int r, int idx, int val){
- if(l==r){
- tree[node] = val;
- return;
- }
- int mid = (l+r)>>1;
- if(idx<=mid) update(node<<1,l,mid,idx,val);
- else update(node<<1|1,mid+1,r,idx,val);
- tree[node] = min(tree[node<<1],tree[node<<1|1]);
- }
- int query(int node, int l, int r, int ll, int rr){
- if(l > rr || r < ll) return 1e9;
- if(l>=ll&&r<=rr) return tree[node];
- int mid = (l+r)>>1;
- return min(query(node<<1,l,mid,ll,rr),query(node<<1|1,mid+1,r,ll,rr));
- }
- void init(){
- memset(dp,0,sizeof dp);
- memset(alt,0,sizeof alt);
- for(int i = 0; i < 4*N; i++) tree[i] = 1e9;
- for(int i = 3; i <= n+1; i++) alt[i] = alt[i-1] + (bool)(s[i]!=s[i-1]);
- }
- int main(){
- #ifndef ONLINE_JUDGE
- readFile;
- #endif
- fastIO;
- int t; cin >> t;
- while(t--){
- cin >> n >> k >> s;
- s = "$$" + s;
- init();
- update(1,1,N,1,0);
- for(int i = 2; i <= n+1; i++){
- dp[i] = dp[i-1] + 1;
- int l = max(i-k,1), r = i-1;
- int e = alt[r+1]-alt[l]+1;
- if((r-l+1)>e){
- int q = query(1,1,N,l-1,r-1);
- dp[i] = min(dp[i],q+1);
- }
- update(1,1,N,i,dp[i]);
- }
- cout << dp[n+1]-1 << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement