百度之星初赛 A 杭电6376 度度熊剪纸条

Love The Way You Lie 2022-05-15 00:37 170阅读 0赞

C 度度熊剪纸条  
链接：[点我][Link 1]  
Problem Description  
度度熊有一张纸条和一把剪刀。纸条上依次写着 N 个数字，数字只可能是 0 或者 1。  
度度熊想在纸条上剪 K 刀（每一刀只能剪在数字和数字之间），这样就形成了 K+1 段。  
他再把这 K+1 段按一定的顺序重新拼起来。不同的剪和接的方案，可能会得到不同的结果。  
度度熊好奇的是，前缀 1 的数量最多能是多少。  
Input  
有多组数据，读到EOF结束。  
对于每一组数据，第一行读入两个数 N 和 K 。

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

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

Sample Input  
5 1  
11010  
5 2  
11010

Sample Output  
2  
3  
同学用贪心过的，首尾的只要一刀，中间要两刀，首尾消耗小，留两刀出来，先把中间的大的砍出来，开一个数组统计，按大小排序，依次砍，最后两刀砍出一个前缀和后缀。

#include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    int num[100005];
    int cmp(int a,int b) {
        return a>b;
    }
    int main() {
        int n,k;
        while(scanf("%d%d",&n,&k)==2) {
            string s;
            cin>>s;
            int all=0,i;  
            for(i=0; i<n; i++)    if(s[i]=='1')  all++;
    
            int pre=0;  
            for(i=0; i<n; i++) {
                if(s[i]=='1')  pre++;
                else  break;
            }
            int left1=0;  
    
            if(pre!=all) {
                for(i=n-1; i>=0; i--) {
                    if(s[i]=='1')  left1++;
                    else  break;
                }
            }
    
    
            memset(num,0,sizeof(num));
            int j=0,flag;
            for(i=pre; i<n-left1; i++) {
                flag=0;
                while(s[i]=='1'&&i<n) {
                    num[j]++;
                    i++;
                    flag=1;
                }
                if(flag)    j++;
            }
            sort(num,num+j,cmp);
    
            int sum=0,cur=k;
            for(i=0; i<j&&cur>2; i++) {
                sum+=num[i];
                num[i]=0;
                cur-=2;
            }
            for(i=0; i<j; i++)  if(num[i]!=0) break;
            if(cur>=2) {
                if(pre<=left1&&pre<=num[i])  sum+=(left1+num[i]);
                else if(left1<=pre&&left1<=num[i])  sum+=(pre+num[i]);
                else  sum+=(left1+pre);
            } else if(cur==1) {
                sum+=max(num[i],pre+left1);
            }
            if(k==0)  printf("%d\n",pre);
            else  printf("%d\n",sum);
        }
        return 0;
    }

此题还有一种解法，就是化作01背包问题，把刀数看成背包容量，需要切的刀数看成物品消耗，然后就可以套01背包了，背包容量要加1，导致k0时，会有特殊情况，就是前缀和后缀有1时，所以要特判，为什么背包容量要加1呢？问得好，这里把中间的1子串花费记为2，但是有的情况不需要砍两下，比如011011101，全部砍出来需要5刀，但是只要4刀就可以达到题目的要求了，5刀就是11,111,1对吧，4刀可以是110,111,1或1110,11,1，所以刀数要加1才能使01背包和题目完美融合，错，还不是完美融合，因为当k0的时候，k加1，如果遇到有前缀和后缀的情况就GG 了，所以就要特判一下，不过如果提前特判不加1也是一样的。  
代码我不想码了（其实是代码能力贼弱，码出来花儿都谢了）哦哦思维能力也弱，呜呜呜，  
所以直接贴大佬的代码了：代码出处：http://www.cnblogs.com/bluefly-hrbust/p/9466541.html

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

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6376