（除草）两道cf题题解
2014-02-19 11:54:56| 分类：
CodeForces
| 标签：
|举报
|字号大中小 订阅
cf的傻逼题实在太多了。。。
不过最近两场的最后一题都挺不错的。。。（不过数据太弱，两题都是随便什么傻逼做法都能过
Rockethon 2014 F
题意：最大k段子段和。。
题解：
费用流很简单。。
暴力用常数很好的堆也能把4*10^6直接过掉。。真心呵呵。。
而且O(nlogn)跑得比O(n)快。。
呵呵。
好了，O(n)的做法是这样的：
首先将负数和正数的连续子段合并，去掉两旁的负数段。。
这样就是+-+-+-+的长度为奇数的正负交错的序列。
做法是每次取出绝对值最小的那段将其和左右的两段合并。。。这样裸搞是O(nlogn)的，得用堆维护。。
但是我们可以观察出这样的性质：
假设我们要进行m次合并（合并一次减少两个数，最终只留下2*k-1个数，算算即可）。。我们可以取出当前段的绝对值前m小的那些段。从理论上来讲，这些段一定是要参与合并的——为什么呢？首先你要进行那么多次合并，但是却不是合并这前m小的，则只可能是一次合并之后得到后形成的新的数取代了之前的位置。。设第m小的段的值为S，则存在某次a+b+c<S。。则a,b,c中必有两个数的绝对值小于等于S，那么本来这儿有两次合并，现在依旧有两次合并，无所谓。还有个问题，就是你必须保证|b|<=|c| && |b|<=|a|。。也就是说，如果说有连续可合并项，还是得从小的开始搞，否则在该段就违背了之前贪心的原则了。。
这样每次至少进行了1/3m次合并。因为某次合并未进行是因为它被两旁的合并了。因为是指数级递减，次数logn，时间复杂度依旧为O(nlogn)。
但是注意到，由于前m次待选合并中至少有1/3m次有效合并，所以那么排在3m之后的那些待选合并就肯定没用了，这样每次只保留前3*m次合并
时间复杂度就是T(m)=3m+T(2/3n)=O(n)
时间是线性的，慢死人。。
round 230 div1 E
题意：
给定长度为n的串，你每次可以删除一个连续子串：1.子串中相邻两个数差为一 2.这个子串是凸的。。
删除长度为l的串得到收益为v_l（v可能为负数）。
求删除方案使得最终收益最大。。删掉一段数后，左右两旁会合起来
题解：
O(n^3)就能过了。。
做法是这样的：
首先，一次删除的数一定是先递增再递减的，而其长度可以根据其左端的数大小，右端数的大小，和最大的那个数的大小计算出来。。
所以可以这么dp：
dp[i][j]表示i到j全部删完的最大收益。
dp1[i][j]表示i到j删完，且在最后一次删除中，i是最小的，j是最大的最大收益。。
dp2[i][j]表示i到j删完，且在最后一次删除中，i是最左的，j是最右的最大收益。。
然后O(n^3)暴算即可
评论这张
转发至微博
转发至微博
关闭
玩LOFTER，免费冲印20张照片，人人有奖！
我要抢>
<#--最新日志，群博日志-->
<#--推荐日志-->
<#--引用记录-->
<#--博主推荐-->
<#--随机阅读-->
<#--首页推荐-->
<#--历史上的今天-->
<#--被推荐日志-->
<#--上一篇，下一篇-->
<#-- 热度 -->
<#-- 网易新闻广告 -->
<#--右边模块结构-->
<#--评论模块结构-->
<#--引用模块结构-->
<#--博主发起的投票-->
评论