[hdoj6376]度度熊剪纸条

度度熊剪纸条

题意

将一段01的序列分成$k$段,将他们重新拼接,问拼接成的纸条中前导0最多有多少个。

  • 拼接不可以改变方向。

题解

我模拟下来就是我们可以将这段序列分成三部分,

比如

11111/0/111/0/1111/0/11111

最前方的1部分和最后方的1部分和中间的1部分。

如果想将中间的1放在前面就必须剪两次,前方和后方的只需要1次。

模拟的话。

  • 我们首先如果第一段不剪,那么就是从后面的中间1和后方1选择,中间1需要剪两次,后方1只要剪一次。

  • 如果第一段剪掉,那么就是选择最大的,在他前面切一刀,把它当做最后的处理,其余的是前面的和后面的剪一刀和中间的剪两刀。

如果$k==0$特殊处理一下。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,k;
const int maxn = 1e4+100;
char s[maxn];
int ve[maxn];
int solve(){
bool flag = 0;
int cnt = 0;
int l = 0,r = 0;
int ans = 0;
int j = 0;
int st = 0,ed = n-1;
while(s[st]==1&&st<n)st++;
l = st;
while(s[ed]==1&&st<=ed) ed--;
r = n-ed-1;
rep(i,st,ed+1){
if(s[i] == 1) cnt++;
if(s[i] == 0 && cnt){
ve[++j] = cnt;
cnt = 0;
}
}
if(k==0) return l;
sort(ve+1,ve+j+1);
while(k>2 && j>=1){
ans += ve[j--];
k-=2;
}
if(k==1){
ans += max(l+r,ve[j]);
}else{
ans += max(l+r,max(l+ve[j],r+ve[j]));
}
return ans;
}
char temp[maxn];
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
while(~scanf("%d%d",&n,&k)){
scanf("%s",s);
rep(i,0,n) s[i] -= '0';
printf("%d\n",solve());
}

return 0;
}