[hdoj6376]度度熊剪纸条

度度熊剪纸条

题意

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

• 拼接不可以改变方向。

题解

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

比如

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

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

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

模拟的话。

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

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

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

ac代码

#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;
}