链接　　http://acm.hdu.edu.cn/showproblem.php?pid=6376

分析

　　这道题好像不是很难，因为是要拼出前缀1，所以确定剪下每一段1需要的刀数，然后因为有次数限制，所以这个问题实际上相当于一个01背包问题，体积换价值，头部和尾部的话需要一刀，中间两刀，但中间的1有一次是可以只用一刀的，剪法就是把它和0一块取出来，当拼出的前缀1的尾部，所以这里不是很好处理，因为我们并不知道在那个地方剪了一刀，于是直接把体积+1就好，这样跑一个01背包就解决问题了？

　　真的嘛？未必哦。01背包的复杂度对于这道题来讲是不对的，极限数据完全可以卡爆，比如下边这组

　　所以继续考虑，真的有必要用背包吗？既然中间的体积都是2，那么我肯定先挑着大的剪啊，这相比不需要解释，所以其实一个nlogn的排序+贪心就能解决，不过这样的话就要写三个个特判，一个是剪0次的时候直接输出前缀1，一种是体积用到最后是1，这样比较一下用前缀和后缀好还是用中间的好，另一个是体积用到最后是2，那我可以选择前缀和后缀，也可以选择中间和前缀，中间和后缀，三者取最大即可。

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int N=1e4+;

 char s[N];int v[N];

 int main(){

     int n,k;

     while(cin>>n>>k>>s){

         int st=,ed=n-,front=,last=;

         while(s[st]==''&&st<n)st++,front++;

         if(k==){

             cout<<front<<endl;

             continue;

         }

         while(s[ed]==''&&ed>=st)ed--,last++;

         int tot=,p=;

         for(int i=st;i<=ed;i++)

             if(s[i]==''){

                 if(tot)v[++p]=tot;

                 tot=;

             }else tot++;

         sort(v+,v+p+);

         int ans=;

         while(k>&&p>=)k-=,ans+=v[p--];

         if(k==)ans+=max(front+last,v[p]);

         else ans+=max(front+last,max(front+v[p],last+v[p]));

         cout<<ans<<endl;

     }

 }

巴特西

HDU-6376 度度熊剪纸条

链接　　http://acm.hdu.edu.cn/showproblem.php?pid=6376

分析

最新文章

热门文章

巴特西

HDU-6376 度度熊剪纸条

链接 http://acm.hdu.edu.cn/showproblem.php?pid=6376

分析

最新文章

热门文章

链接　　http://acm.hdu.edu.cn/showproblem.php?pid=6376