题意描述
思路
观察发现，满足题目要求的字符串序列是由前
x
1
x_{1}
x1个
0
0
0，中间
x
2
x_{2}
x2长度的周期串，最后
x
3
x_{3}
x3个0组成的。我们使用
f
[
i
]
f[i]
f[i]表示第
i
i
i个位置是
1
1
1时的最小次数.计算将
[
1
,
i
−
1
]
[1,i-1]
[1,i−1]变成
0
0
0的代价。如果
i
>
k
i>k
i>k，则以
f
[
i
−
k
]
f[i-k]
f[i−k]为基础，再计算以上代价，最后加上将
[
i
+
1
,
n
]
[i+1,n]
[i+1,n]变成0的代价取
m
i
n
min
min即可。对于变成
0
0
0的代价，可以使用前缀和来进行优化。 转移方程：
f
[
i
]
=
s
u
m
[
i
−
1
]
+
c
h
e
c
k
(
s
[
i
]
)
f[i]=sum[i-1]+check(s[i])
f[i]=sum[i−1]+check(s[i])
i
f
(
i
>
k
)
f
[
i
]
=
m
i
n
(
f
[
i
]
,
f
[
i
−
k
]
+
s
u
m
[
i
−
1
]
−
s
u
m
[
i
−
k
]
+
c
h
e
c
k
(
s
[
i
]
)
if(i>k) f[i]=min(f[i],f[i-k]+sum[i-1]-sum[i-k]+check(s[i])
if(i>k)f[i]=min(f[i],f[i−k]+sum[i−1]−sum[i−k]+check(s[i])
AC代码
#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std
;
typedef unsigned long long ull
;
typedef pair
<int,int> PII
;
typedef pair
<long,long> PLL
;
typedef pair
<char,char> PCC
;
typedef long long ll
;
const int N
=1e6+10;
const int M
=1e6+10;
const int INF
=0x3f3f3f3f;
const int MOD
=1e9+7;
char s
[N
];
int sum
[N
],f
[N
];
void solve(){
int n
,k
;cin
>>n
>>k
;
cin
>>s
+1;
rep(i
,1,n
+1){
if(s
[i
]=='1'){
sum
[i
]=sum
[i
-1]+1;
}else sum
[i
]=sum
[i
-1];
}
if(sum
[n
]<=1){
cout
<<0<<endl
;
return;
}
int ans
=sum
[n
]-1;
rep(i
,1,n
+1){
f
[i
]=sum
[i
-1]+(s
[i
]!='1');
if(i
>k
) f
[i
]=min(f
[i
],f
[i
-k
]+sum
[i
-1]-sum
[i
-k
]+(s
[i
]!='1'));
ans
=min(ans
,f
[i
]+sum
[n
]-sum
[i
]);
}
cout
<<ans
<<endl
;
}
int main(){
IOS
;
int t
;cin
>>t
;
while(t
--)
solve();
return 0;
}
