显然DP题...
f[i][0]表示这个点不装路由器，f[i][1]表示装路由器
转移也很简单，在前面一段区间找最小值就好了
但是直接转移是$O(n*k)$的，会T掉
大佬说这个东西有单调性，但是菜鸡我找不到，因为是区间问题，所以线段树强上
区间查询+单点修改
1 #include<bits/stdc++.h>
2 #define int long long
3 #define inf (0x7f7f7f7f7f7f7f)
4 using namespace std;
5 inline int read(){
6 int ans=0,f=1;char chr=getchar();
7 while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
8 while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
9 return ans*f;
10 }const int M = 2e5+5;
11 struct Segment_Tree{
12 int s[M<<2];
13 #define mid (l+r>>1)
14 #define ls (i<<1)
15 #define rs (i<<1|1)
16 inline void Push_Up(int i){s[i]=min(s[ls],s[rs]);}
17 void Build(int i,int l,int r){
18 if(l==r)return (void)(s[i]=inf);
19 Build(ls,l,mid),Build(rs,mid+1,r);
20 Push_Up(i);
21 }void Update(int i,int l,int r,int pos,int x){
22 if(l==r)return (void)(s[i]=min(s[i],x));
23 if(pos<=mid) Update(ls,l,mid,pos,x);
24 else Update(rs,mid+1,r,pos,x);
25 Push_Up(i);
26 }int Query(int i,int l,int r,int ql,int qr){
27 if(ql<=l&&r<=qr)return s[i];
28 int t1=inf,t2=inf;
29 if(ql<=mid) t1=Query(ls,l,mid,ql,qr);
30 if(qr>mid) t2=Query(rs,mid+1,r,ql,qr);
31 return min(t1,t2);
32 }
33 }T1,T2;
34 char s[M];
35 int n,m,k,f[M][2];
36 signed main(){
37 n=read(),k=read();
38 scanf("%s",s+2);
39 T1.Build(1,1,n),T2.Build(1,1,n);
40 memset(f,0x3f,sizeof(f));
41 T2.Update(1,1,n,1,f[1][0]=f[1][1]=0);
42 for(int i=2;i<=n+1;i++){
43 f[i][0]=T1.Query(1,1,n,max(i-k,1ll),i-1);
44 if(s[i]=='1') f[i][1]=T2.Query(1,1,n,max(1ll,i-k-1),i-1)+i-1;
45 else f[i][1]=min(T1.Query(1,1,n,max(1ll,i-k-1),i-1),min(f[i-1][0],f[i-1][1]))+i-1;
46 T2.Update(1,1,n,i,min(f[i][0],f[i][1]));
47 if(s[i]=='1') T1.Update(1,1,n,i,f[i][1]);
48 }cout<<min(f[n+1][0],f[n+1][1]);
49 return 0;
50 }