Posted on 2011-10-05 09:42
Mato_No1 阅读(1585)
评论(0) 编辑 收藏 引用 所属分类:
BZOJ
【1】
BZOJ1571DP题，写起来比较繁琐……
首先转移方程是不难想的囧……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]中找；
代码