题意：

一张纸条上依次写着N个数字，数字只可能是0或者1。在纸条上剪K刀，这样就形成了K+1段，再把这K+1段按一定的顺序重新拼起来。问前缀 1 的数量最多能是多少。

思路：

分类讨论不会啊…太菜了啊QAQ

看了题解有一种dp的做法，这比较好理解。

要把这个01串原本的前缀1剪下来只要剪1次，把原本的后缀1剪下来也要剪1次，中间的一串1剪下来要剪2次，所以这就是一个背包问题了，但是比如1101110011，如果这种策略的话要使前缀最大至少要5次，事实上只要4次，因为11100只要剪一次，放在最后面就可以了，所以事实上可以剪k+1次。

这里注意要特判全是1和k为0的情况。

代码：

char a[10010];
int w[10010];
int v[10010];
int dp[10010];
int main()
{
    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        scanf("%s",a);
        int len=strlen(a);
        int s,e;
        int cnt=0;
        int sign=0;
        for(int i=0;i<len&&sign==0;i++)
            if(a[i]!='1')sign++;
        if(sign==0)
        {
            printf("%d\n",len);
            continue;
        }
        for(int i=0;i<len;i++)
        {
            if(a[i]!='1')
            {
                s=i;
                if(i!=0)
                {
                    v[++cnt]=i;
                    w[cnt]=1;
                }
                break;
            }
        }
        if(k==0){printf("%d\n",v[cnt]);continue;}
        for(int i=len-1;i>=0;i--)
        {
            if(a[i]!='1')
            {
                e=i;
                if(i!=len-1)
                {
                    v[++cnt]=len-1-i;
                    w[cnt]=1;
                }
                break;
            }
        }
        int l=0;
        for(int i=s;i<=e;i++)
        {
            if(a[i]=='0')
            {
                if(l!=0)
                {
                    v[++cnt]=l;
                    w[cnt]=2;
                }
                l=0;
            }
            else l++;
        }
        //for(int i=1;i<=cnt;i++)
            //printf("%d %d\n",w[i],v[i]);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=cnt;i++)
        {
            for(int j=k+1;j>=w[i];j--)
            {
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        printf("%d\n",dp[k+1]);
    }
    return 0;
}