SHARE
TWEET

Untitled

a guest May 12th, 2016 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define readFile freopen("in.txt","r",stdin)
  4. #define writeFile freopen("out.txt","w",stdout)
  5. #define fastIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  6.  
  7. using namespace std;
  8.  
  9. const int N = 100010;
  10.  
  11. int dp[N], tree[4*N], alt[N];
  12. int n,k;
  13. string s;
  14.  
  15. void update(int node, int l, int r, int idx, int val){
  16.     if(l==r){
  17.         tree[node] = val;
  18.         return;
  19.     }
  20.     int mid = (l+r)>>1;
  21.     if(idx<=mid) update(node<<1,l,mid,idx,val);
  22.     else update(node<<1|1,mid+1,r,idx,val);
  23.     tree[node] = min(tree[node<<1],tree[node<<1|1]);
  24. }
  25.  
  26. int query(int node, int l, int r, int ll, int rr){
  27.     if(l > rr || r < ll) return 1e9;
  28.     if(l>=ll&&r<=rr) return tree[node];
  29.     int mid = (l+r)>>1;
  30.     return min(query(node<<1,l,mid,ll,rr),query(node<<1|1,mid+1,r,ll,rr));
  31. }
  32.  
  33. void init(){
  34.     memset(dp,0,sizeof dp);
  35.     memset(alt,0,sizeof alt);
  36.     for(int i = 0; i < 4*N; i++) tree[i] = 1e9;
  37.     for(int i = 3; i <= n+1; i++) alt[i] = alt[i-1] + (bool)(s[i]!=s[i-1]);
  38. }
  39.  
  40. int main(){
  41. #ifndef ONLINE_JUDGE
  42.     readFile;
  43. #endif
  44.     fastIO;
  45.     int t; cin >> t;
  46.     while(t--){
  47.         cin >> n >> k >> s;
  48.         s = "$$" + s;
  49.         init();
  50.         update(1,1,N,1,0);
  51.         for(int i = 2; i <= n+1; i++){
  52.             dp[i] = dp[i-1] + 1;
  53.             int l = max(i-k,1), r = i-1;
  54.             int e = alt[r+1]-alt[l]+1;
  55.             if((r-l+1)>e){
  56.                 int q = query(1,1,N,l-1,r-1);
  57.                 dp[i] = min(dp[i],q+1);
  58.             }
  59.             update(1,1,N,i,dp[i]);
  60.         }
  61.         cout << dp[n+1]-1 << "\n";
  62.     }
  63.     return 0;
  64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top