背包问题.doc

1、Robberies http:/ 背包;第一次做的时候把概率当做背包 (放大 100000 倍化为整数):在此范围内最多能抢多少钱 最脑残的是把总的概率以为是抢 N 家银行的概率之和 把状态转移方程写成了fj=maxfj,fj-qi.v+qi.money(fj表示在概率 j 之下能抢的大洋);正确的方程是:fj=max(fj,fj-qi.money*qi.v) 其中,fj 表示抢 j 块大洋的最大的逃脱概率,条件是 fj-qi.money可达,也就是之前抢劫过;始化为:f0=1, 其余初始化为 -1 (抢 0 块大洋肯定不被抓嘛)最大报销额 http:/ 又一个背包问题,对于每张发票,要么报销

2、,要么不报销,0-1 背包,张数即为背包;转移方程:fj=max(fj,fj-1+vi);恶心地方:有这样的输入数据 3 A:100 A:200 A:300最大连续子序列 http:/ sum http:/ 同上,最大连续子序列 Largest Rectangle http:/ 其中,j=heighti;找 j,k 成为关键,一般方法肯定超时,利用动态规划,如果它左边高度大于等于它本身,那么它左边的左边界一定满足这个性质,再从这个边界的左边迭代下去for(i=1;i=ai)li=lli-1;for(i=n;i=1;i-)while(ari+1=ai)ri=rri+1;City Game htt

3、p:/ 的加强版,把 2 维转换化成以每一行底,组成的最大面积;(注意处理连续与间断的情况);Bone Collector http:/ 简单 0-1 背包,状态方程:fj=max(fj,fj-vi+wi)Super Jumping http:/ 最大递增子段和,状态方程:sumj=maxsumi+aj; 其中,0=vi 数塔 http:/ 免费馅饼 http:/ Need A Offer http:/ 0-1 背包,题目要求的是至少收到一份 Offer 的最大概率 ,我们得到得不到的最小概率即可,状态转移方程:fj=min(fj,fj-vi*wi);其中,wi表示得不到的概率,(1-fj)为

4、花费 j元得到 Offer 的最大概率 FATE http:/ 二维完全背包,第二层跟第三层的要顺序循环;(0-1 背包逆序循环);状态可理解为,在背包属性为 m(忍耐度), s(杀怪个数) 里最多能得到的经验值,之前的背包牺牲体积,这个背包牺牲忍耐度跟个数注意: 最后扫的时候 外层循环为忍耐度 ,内层循环为杀怪个数,因为题目要求出剩余忍耐度最大,没有约束杀怪个数,一旦找到经验加满的即为最优解;状态转移方程为: fjk=max(fjk,fj-vik-1+wi); wi表示杀死第 i 个怪所得的经验值,vi表示消耗的忍耐度How To Type http:/ 用两个 a,b 数组分别记录 Cap

5、s Lock 开与关时打印第 i 个字母的最少操作步骤;而对于第 i 个字母的大小写还要分开讨论 :Chi为小写: ai=min(ai-1+1,bi-1+2);不开灯直接字母,开灯则先关灯再按字母,最后保持不开灯; bi=min(ai-1+2,bi-1+2);不开灯则先按字母再开灯 ,开灯则 Shift+字母(比关灯,按字母再开灯节省步数),最后保持开灯 ;Chi为大写: ai=min(ai-1+2,bi-1+2); bi=min(ai-1+2,bi-1+1)最后,blen-1+, 关灯嘛 O(_)O Coins http:/ HDU1171 Big Event In HDU,一维 DP,可达

6、可不达 Beans http:/ 横竖分别求一下不连续的最大子段和;状态方程: Sumi=max(sumj)+ai;其中,0=heighti的个数即可,这里用 hash+滚动,先求出 heighti出现的次数,然后逆序扫一遍 hashi+=hashi+1; 最少拦截系统 http:/ DP;if(vimaxdpj) (0j*2 时,Dpij = min(Dpi-1j,Dpi-2j-1+(wj-wj-1)2) Humble Numbers http:/ 如果一个数是 Humble Number,那么它的 2 倍,3 倍,5 倍,7 倍仍然是 Humble Number定义 Fi为第 i 个 Hu

7、mble NumberFn=min(2*fi,3*fj,5*fk,7*fL), i,j,k,L 在被选择后相互移动(通过此题理解到数组有序特性) Doing Homework Again http:/ 这题为贪心,经典题;切题角度,对于每个任务要么在截至日期前完成要么被扣分;所以考虑每个人物的完成情况即可;由于每天只能完成一个任务 ,所以优先考虑分值较大的任务,看看该任务能不能完成,只要能完成,即使提前完成,占了其他任务的完成日期也没关系,因为当前任务的分值最大嘛,而对于能完成的任务能拖多久就拖多久,以便腾出更多时间完成其他任务; How Many Ways http:/ 两种 D 法,一是对

8、于当前的点 ,那些点可达;二是当前点可达那些点;明显第二种方法高,因为第一种方法有一些没必要的尝试;Dpij+=Dpiijj; (mapiijj=两点的曼哈顿距离)值得优化的地方,每两点的曼哈顿距离可能不止求一次,所以预处理一下直接读取 珍惜现在 感恩生活 http:/ 每个物品最多可取 n 件,多重背包;利用二进制思想,把每种物品转化为几件物品,然后就成为了 0-1 背包 Piggy-Bank http:/ 完全背包;常规背包是求最大值 ,这题求最小值;只需要修改一下初始化,f0=0,其他赋值为+即可;状态转移方程:fiV=maxfi-1V,fi-1V-k*vi+k*wi,其中 0m 时,

9、Summn=maxSumm-1k,Summn-1+vn; 其中,m-1wj否则在 dp中找到最大的 j,满足 dpjMaxNumi之后无意义,无谓的浪费 记 Max_n=MaxNumi;Dpi-1中的每一项都可能影响到 Dpi,即使 Numi-1j 时, 解雇 然后求出最小值Dpij=minDpi-1kMax_n+(招聘,解雇,工资); Dividing http:/ 一维 Dp Sum 为偶数的时候判断 Dpsum/2可不可达 Human Gene Factions http:/ 状态转移方程:fij=Max(fi-1j-1+raibj, fij-1+r-bj,fi-1j+rai-); Do

10、ing Homework http:/ 这题用到位压缩;那么任务所有的状态有 2n-1 种状态方程为:Dpnext=minDpk+i 的罚时 其中,next=k+(1i 的奇偶性决定状态 k具体实现为: 对每种状态遍历 n 项任务,如果第 i 项没有完成 ,则计算出 Dpnext的最优解 Free DIY Tour http:/ 简单的数塔 Dp,考察的是细节的处理 ;Dpi=MaxDpj+vi 其中 j-i 为通路;vn+1有没有初始化,Dp 数组有没有初始化这题不能用想当然的”最长路”来解决,这好像是个 NP 问题 解决不了的重温世界杯 http:/ 这题的状态不难理解,状态表示为,如果上

11、一个城市剩下的钱不为负,也就是没有被赶回杭电,则再考虑它对下一个城市的影响;如果上一个城市剩下的前加上当前城市的前大于当前城市的生活费,那么 Dpi=Dpi-1+1;值得注意的而是这题的数据为 100000;不可能以每个城市为起点来一次 Dp,时间复杂度为n2;足已超时;我是这样处理的,在保存的数据后面再接上 1n 的数据,这样扫描一遍的复杂度为 n;再加一个优化,当 Dpi=n 时,也就是能全部游完所有城市的时候,直接 break;Pearls http:/ Dpi=minDpj+V, 0=b=c; Advanced Fruits http:/ 最长公共子序列的加强版 本文来自 CSDN 博客，转载请标明出处：http:/