百度之星-day1-1003-度度熊剪纸条

时间：2023-03-09 20:31:03
百度之星-day1-1003-度度熊剪纸条

度度熊剪纸条

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 个数。

0≤K<N≤10000

所有数据 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 =;

struct node

{

    int cost,val;

} one[maxx];

char a[maxx];

bool b[maxx];

int dp[maxx];

int main()

{

    int n,k;

    int ans=;

    int pre;

    int bak;

    while(~scanf("%d%d",&n,&k))

    {

        ans=;

        pre=;

        bak=;

        memset(one,,sizeof(one));

        scanf("%s",a);

        int len=strlen(a);

        for(int i=; i<=len; i++)

        {

            if (a[i-]=='')

            {

                b[i]=;

            }

            else

            {

                b[i]=;

            }

        }

        if (b[]==)pre=;

        if (b[n]==)bak=;

        int flag=;

        int cnt=;

        one[].cost=;

        for (int i=; i<=len; i++)

        {

            if (flag== && b[i]==){

                continue;

            }

            else if (b[i]== && (flag== || flag==))

            {

                one[cnt].val++;

                flag=;

                continue;

            }

            else if (b[i]== && flag==)

            {

                one[++cnt].val++;

                one[cnt].cost=;

                flag=;

                continue;

            }

            if (b[i]== && (flag== || flag==))

            {

                flag=;

                continue;

            }

        }

        if (pre)one[].cost=;

        if (bak)one[cnt].cost=;

        memset(dp,,sizeof(dp));

        //特判0

        if(k==){

            if (pre){

                printf("%d\n",one[].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=;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 ;

}

相关文章