度度熊剪纸条

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1397    Accepted Submission(s): 206


Problem Description
度度熊有一张纸条和一把剪刀。

纸条上依次写着  N 个数字,数字只可能是 0 或者 1

度度熊想在纸条上剪 K 刀(每一刀只能剪在数字和数字之间),这样就形成了 K+1 段。

他再把这 K+1 段按一定的顺序重新拼起来。

不同的剪和接的方案,可能会得到不同的结果。

度度熊好奇的是,前缀 1 的数量最多能是多少。
 

 

Input
有多组数据,读到EOF结束。

对于每一组数据,第一行读入两个数  N 和 K 。

第二行有一个长度为 N 的字符串,依次表示初始时纸条上的 N 个数。

0K<N10000

所有数据 N 的总和不超过100000
 

 

Output
对于每一组数据,输出一个数,表示可能的最大前缀  1 的数量。
 

 

Sample Input
5 1 11010 5 2 11010
 

 

Sample Output
2 3
 

 

Source
 
 
 
最开始想贪贪心,排序过,后来发现被坑了。。。TMD想到背包都不敢写,害得我复赛都没进。。。最前面是1只需要减一次的如111000,最后面是1也只需要减去1次,00001111,有人肯定觉得。。。0001100也减出一次就行了,但是。。。这种减法就。。。比较坑了 ,我们可以想想,这种减去了。。。后面就是0了,这样拼接就比较麻烦。。。我们不妨这样想。。。我们整个过程只最多满足一个不是1111类型的,而是111110000这种后面接0 的,这种减是只需要一次了,但是还有一个问题,如果我把中间的一个在能切割的范围内放在最后,那么就少切割一次,意思就是 011001111001 这样的一个串,我可以用5 次切出来全部是1 但是实际上我只需要切4次就可以,因为我可以将11放最后或者将1111放最后,也就是组成的串为1,11,111100,00,0 或者 1,1111,1100,00,0;为了满足这种情况,我们把背包容量+1,除了前导全是1,后导全是1的费用为1 ,其他费用为2,即可,跑一个01背包岂不是美滋滋???不好意思我的写法比较菜。。。这样特判会造成一种特殊情况,就是K=0时,因为我是把背包容量++,尼玛K=1,要是有前导1或者后导1,岂不是GG??特判即可。。。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxx =100007;
struct node
{
    int cost,val;
} one[maxx];
char a[maxx];
bool b[maxx];
int dp[maxx];
int main()
{
    int n,k;
    int ans=0;
    int pre;
    int bak;
    while(~scanf("%d%d",&n,&k))
    {
        ans=0;
        pre=0;
        bak=0;
        memset(one,0,sizeof(one));
        scanf("%s",a);
        int len=strlen(a);
        for(int i=1; i<=len; i++)
        {
            if (a[i-1]=='0')
            {
                b[i]=0;
            }
            else
            {
                b[i]=1;
            }
        }
        if (b[1]==1)pre=1;
        if (b[n]==1)bak=1;
        int flag=3;
        int cnt=1;
        one[1].cost=2;
        for (int i=1; i<=len; i++)
        {
            if (flag==3 && b[i]==0){
                continue;
            }
            else if (b[i]==1 && (flag==1 || flag==3))
            {
                one[cnt].val++;
                flag=1;
                continue;
            }
            else if (b[i]==1 && flag==0)
            {
                one[++cnt].val++;
                one[cnt].cost=2;
                flag=1;
                continue;
            }
            if (b[i]==0 && (flag==1 || flag==3))
            {
                flag=0;
                continue;
            }
        }
        if (pre)one[1].cost=1;
        if (bak)one[cnt].cost=1;
        memset(dp,0,sizeof(dp));
        //特判0
        if(k==0){
            if (pre){
                printf("%d\n",one[1].val);
            }else{
                printf("0\n");
            }
            continue;
         }
//        for (int i=1;i<=cnt;i++){
//            cout<<one[i].val<<" "<<one[i].cost<<endl;
//        }
        //01背包
        k++;
        for (int i=1;i<=cnt;i++){
           for (int j=k;j>=one[i].cost;j--){
             dp[j]=max(dp[j],dp[j-one[i].cost]+one[i].val);
           }
        }
        printf("%d\n",dp[k]);
    }
    return 0;
}