最近在BZOJ上的刷题总结

Posted on 2011-10-05 09:42 Mato_No1 阅读(1463) 评论(0)  编辑 收藏 引用 所属分类: BZOJ
【1】BZOJ1571
DP题,写起来比较繁琐……
首先转移方程是不难想的囧……F[i][j],表示i时间后能力为j,
然后要设一些辅助数组,G[i]表示F[i][1..MAXJ]的最大值,H2[i]表示能力不超过i的一次滑雪的最小时间(这个还要用一个H1[i]表示能力刚好为i的来辅助求出)……
剩下的也就傻掉了,
当然,WJMZBMR神犇用记忆化搜索……省去了一些计算量……有效缩短时间……Orz啊……
(其实,如果大多数状态都是无效状态或者根本导不出最优解的状态,可以用记忆化的……)
代码

【2】BZOJ1572
任务调度问题(贪心模型)的加强版,用堆优化囧……
先把所有的任务按照结束时间递减排序,然后扫描,对于当前任务A[i],结束时间为T[i],上一个任务A[i-1]的结束时间为T[i-1],设D=T[i-1]-T[i],则在堆中取出收益最大的D个任务(显然该堆是以收益为关键字的大顶堆),用它们填上[T[i]+1, T[i-1]]这个时间段(原因很简单,A[i]及以后的任务在T[i]时刻以前就结束了,不能插入到此段内,因此此段内只能插入A[i-1]及其以前的,也就是在堆中的任务),若堆中的任务数<D,则全部取出,进行完这一步后,再将A[i]插入到堆中即可。
总时间复杂度:O(NlogN);
代码

【3】BZOJ1574
很容易想到最小点割(怎么看怎么像囧),但它和最小点割又不一样,因为本题是求T部分点数最少的点割……
正解仍然是贪心。对于每个报告点,由于它没坏且到1没有只经过未坏点的路径,所以与它相邻的所有的点要么是坏点,要么到1也没有路径,因此可以认为它们都是坏点(在最优方案中一定是这样),这样标记出所有的坏点以后,从1开始做一次遍历(只经过未坏点的),最终结果就是遍历到的点数;
代码

【4】BZOJ1575
裸的DP题啊啊……关键是本沙茶WA了N次还用暴搜代码来对拍啊啊……被折磨死了啊啊……
简单讲一下易疵点:
<1>不可把两边都加上一个0来简化,因为前两条(处理两边的)规则和加上0之后的并不等价;
<2>注意边界点(i=0或j=1时)的情况;
<3>注意最终结果,要在F[0..N-1]中找最小的合法的j而不是只在F[N-1]中找;
代码

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理