免费网站模板网,通江网站建设,泰安市人才交流服务中心,上海网站科技DP是难点#xff0c;供自已以后系统学习。 1.Robberies 连接 #xff1a;http://acm.hdu.edu.cn/showproblem.php?pid2955 背包;第一次做的时候把概率当做背包(放大100000倍化为整数):在此范围内最多能抢多少钱 最脑残的是把总的概率以为是抢N家银行的概率之和… 把状… DP是难点供自已以后系统学习。 1.Robberies 连接 http://acm.hdu.edu.cn/showproblem.php?pid2955 背包;第一次做的时候把概率当做背包(放大100000倍化为整数):在此范围内最多能抢多少钱 最脑残的是把总的概率以为是抢N家银行的概率之和… 把状态转移方程写成了f[j]max{f[j],f[j-q[i].v]q[i].money}(f[j]表示在概率j之下能抢的大洋); 正确的方程是:f[j]max(f[j],f[j-q[i].money]*q[i].v) 其中,f[j]表示抢j块大洋的最大的逃脱概率,条件是f[j-q[i].money]可达,也就是之前抢劫过; 始化为:f[0]1,其余初始化为-1 (抢0块大洋肯定不被抓嘛) 参考代码 连接http://blog.sina.com.cn/s/blog_6cf509db0100sqgx.html 2.最大报销额 连接http://acm.hdu.edu.cn/showproblem.php?pid1864 又一个背包问题,对于每张发票,要么报销,要么不报销,0-1背包,张数即为背包; 转移方程:f[j]max(f[j],f[j-1]v[i]); 恶心地方:有这样的输入数据 3 A:100 A:200 A:300 但本人觉得整理出每张发票的总额作为这件物品的价值也作为容量相当于物品的体积放到容量为q的背包中这就是标准的0—1背包了 转移方程dp[j]max(dp[j],dp[j-sum[i]]sum[i]); 参考代码 连接http://blog.sina.com.cn/s/blog_6cf509db0100su4z.html 3.最大连续子序列 题目连接http://acm.hdu.edu.cn/showproblem.php?pid1231 状态方程:sum[i]max(sum[i-1]a[i],a[i]);最后从头到尾扫一遍。 也可以写成: Maxa[0]; Current0; for(i0;in;i) { if(Current0) Currenta[i]; else Currenta[i]; if(CurrentMax) MaxCurrent; } 参考代码 连接http://blog.sina.com.cn/s/blog_6cf509db0100swfb.html 4.max sum 题目连接http://acm.hdu.edu.cn/showproblem.php?pid1003 同上,最大连续子序列 参考代码 连接http://blog.sina.com.cn/s/blog_6cf509db0100swj7.html 5.Largest Rectangle 连接http://acm.hdu.edu.cn/showproblem.php?pid1506 对于每一块木板,Areaheight[i]*(j-k1) 其中,jxk,height[x]height[i];找j,k成为关键,一般方法肯定超时,利用动态规划,如果它左边高度大于等于它本身,那么它左边的左边界一定满足这个性质,再从这个边界的左边迭代下去主要思路就是找出以当前点位最低点能左右延伸的最长距离,也就是找出最左最右的下标最后的 ans maxs[i]*(r[i]-l[i]1)) (1in! for(i1;in;i) { while(a[l[i]-1]a[i]) l[i]l[l[i]-1]; } for(in;i1;i--) { while(a[r[i]1]a[i]) r[i]r[r[i]1]; } 参考代码 连接http://blog.sina.com.cn/s/blog_6cf509db0100swrb.html 6.City Game 连接http://acm.hdu.edu.cn/showproblem.php?pid1505 1506的加强版,把2维转换化成以每一行底,组成的最大面积;(注意处理连续与间断的情况); 参考代码 连接http://blog.sina.com.cn/s/blog_6cf509db0100sx1z.html 7.Bone Collector 连接http://acm.hdu.edu.cn/showproblem.php?pid2602 简单0-1背包,状态方程:f[j]max(f[j],f[j-v[i]]w[i]) 参考代码 连接http://blog.sina.com.cn/s/blog_6cf509db0100t0il.html 8.Super Jumping 连接http://acm.hdu.edu.cn/showproblem.php?pid1087 最大递增子段和,状态方程:sum[j]max{sum[i]}a[j]; 其中,0ij,a[i]a[j] 参考代码 连接http://blog.sina.com.cn/s/blog_6cf509db0100t1bp.html 9.命运 连接http://acm.hdu.edu.cn/showproblem.php?pid2571 状态方程:sum[i][j]max{sum[i-1][j],sum[i][k]}v[i][j];其中1kj-1,且k是j的因子 参考代码 连接http://blog.sina.com.cn/s/blog_6cf509db0100t3sb.html 10.Monkey And Banana 连接http://acm.hdu.edu.cn/showproblem.php?pid1069 状态方程:f[j]max{f[i]}v[j];其中,0ij,w[i]w[j],h[i]h[j] 参考代码 连接http://blog.sina.com.cn/s/blog_6cf509db0100tymn.html 11.Big Event in HDU 连接http://acm.hdu.edu.cn/showproblem.php?pid1171 一维背包,逐个考虑每个物品带来的影响,对于第i个物品:if(f[j-v[i]]0) f[j]0; 其中,j为逆序循环,且jv[i] 12.数塔 连接http://acm.hdu.edu.cn/showproblem.php?pid2084 自底向上:dp[i][j]max(dp[i1][j],dp[i1][j1])v[i][j]; 13.免费馅饼 连接http://acm.hdu.edu.cn/showproblem.php?pid1176 简单数塔 自底向上计算:dp[i][j]max(dp[i1][j-1],dp[i1][j],dp[i1][j1])v[i][j];处理边界 14.I Need A Offer 连接http://acm.hdu.edu.cn/showproblem.php?pid1203 简单0-1背包,题目要求的是至少收到一份Offer的最大概率,我们得到得不到的最小概率即可,状态转移方程:f[j]min(f[j],f[j-v[i]]*w[i]);其中,w[i]表示得不到的概率,(1-f[j])为花费j元得到Offer的最大概率 15.FATE 连接http://acm.hdu.edu.cn/showproblem.php?pid2159 二维完全背包,第二层跟第三层的要顺序循环;(0-1背包逆序循环);状态可理解为,在背包属性为 {m(忍耐度), s(杀怪个数)} 里最多能得到的经验值,之前的背包牺牲体积,这个背包牺牲忍耐度跟个数 注意: 最后扫的时候 外层循环为忍耐度,内层循环为杀怪个数,因为题目要求出剩余忍耐度最大,没有约束杀怪个数,一旦找到经验加满的即为最优解; 状态转移方程为: f[j][k]max(f[j][k],f[j-v[i]][k-1]w[i]); w[i]表示杀死第i个怪所得的经验值,v[i]表示消耗的忍耐度 16.How To Type 连接http://acm.hdu.edu.cn/showproblem.php?pid2577 用两个a,b数组分别记录Caps Lock开与关时打印第i个字母的最少操作步骤; 而对于第i个字母的大小写还要分开讨论: Ch[i]为小写: a[i]min(a[i-1]1,b[i-1]2);不开灯直接字母,开灯则先关灯再按字母,最后保持不开灯; b[i]min(a[i-1]2,b[i-1]2);不开灯则先按字母再开灯,开灯则Shift字母(比关灯,按字母再开灯节省步数),最后保持开灯; Ch[i]为大写: a[i]min(a[i-1]2,b[i-1]2); b[i]min(a[i-1]2,b[i-1]1) 最后,b[len-1],关灯嘛O(∩_∩)O~ 17.Coins 连接http://acm.hdu.edu.cn/showproblem.php?pid2844 类似于HDU1171 Big Event In HDU,一维DP,可达可不达 18.Beans 连接http://acm.hdu.edu.cn/showproblem.php?pid2845 横竖分别求一下不连续的最大子段和; 状态方程: Sum[i]max(sum[j])a[i];其中,0ji-1; 19.Largest Submatrix 连接http://acm.hdu.edu.cn/showproblem.php?pid2870 枚举a,b,c 最大完全子矩阵,类似于HDU1505 1506 20.Matrix Swapping II 连接http://acm.hdu.edu.cn/showproblem.php?pid2830 最大完全子矩阵,以第i行为底,可以构成的最大矩阵,因为该题可以任意移动列,所以只要大于等于height[i]的都可以移动到一起,求出heightheight[i]的个数即可,这里用hash滚动,先求出height[i]出现的次数,然后逆序扫一遍hash[i]hash[i1]; 21.最少拦截系统http://acm.hdu.edu.cn/showproblem.php?pid1257 两种做法,一是贪心,从后往前贪;二是DP; if(v[i]max{dp[j]}) (0jlen) dp[len]v[i]; 22.Common Subsequence http://acm.hdu.edu.cn/showproblem.php?pid1159 经典DP,最长公共子序列 Len[i][j]{len[i-1][j-1]1,(a[i]b[j]); max(len[i-1][j],len[i][j-1])} 初始化的优化: for(i0;ia;i) for(j0;jb;j) len[i][j]0; for(i1;ia;i) for(j1;jb;j) if(ch1[i-1]ch2[j-1]) len[i][j]len[i-1][j-1]1; else len[i][j]max(len[i-1][j],len[i][j-1]); 23.搬寝室http://acm.hdu.edu.cn/showproblem.php?pid1421 状态Dp[i][j]为前i件物品选j对的最优解 当ij*2时,只有一种选择即 Dp[i-2][j-1](w[i]-w[i-1])^2 当ij*2时,Dp[i][j] min(Dp[i-1][j],Dp[i-2][j-1](w[j]-w[j-1])^2) 24.Humble Numbers http://acm.hdu.edu.cn/showproblem.php?pid1058 如果一个数是Humble Number,那么它的2倍,3倍,5倍,7倍仍然是Humble Number 定义F[i]为第i个Humble Number F[n]min(2*f[i],3*f[j],5*f[k],7*f[L]), i,j,k,L在被选择后相互移动 (通过此题理解到数组有序特性) 25.Doing Homework Again http://acm.hdu.edu.cn/showproblem.php?pid1789 这题为贪心,经典题; 切题角度,对于每个任务要么在截至日期前完成要么被扣分;所以考虑每个人物的完成情况即可;由于每天只能完成一个任务,所以优先考虑分值较大的任务,看看该任务能不能完成,只要能完成,即使提前完成,占了其他任务的完成日期也没关系,因为当前任务的分值最大嘛,而对于能完成的任务能拖多久就拖多久,以便腾出更多时间完成其他任务; 26.How Many Ways http://acm.hdu.edu.cn/showproblem.php?pid1978 两种D法,一是对于当前的点,那些点可达;二是当前点可达那些点; 明显第二种方法高,因为第一种方法有一些没必要的尝试; Dp[i][j]Dp[ii][jj]; (map[ii][jj]两点的曼哈顿距离) 值得优化的地方,每两点的曼哈顿距离可能不止求一次,所以预处理一下直接读取 27.珍惜现在 感恩生活http://acm.hdu.edu.cn/showproblem.php?pid2191 每个物品最多可取n件,多重背包; 利用二进制思想,把每种物品转化为几件物品,然后就成为了0-1背包 28.Piggy-Bank http://acm.hdu.edu.cn/showproblem.php?pid1114 完全背包;常规背包是求最大值,这题求最小值; 只需要修改一下初始化,f[0]0,其他赋值为∞即可; 状态转移方程:f[i][V]max{f[i-1][V],f[i-1][V-k*v[i]]k*w[i]},其中0k*v[i]V 29.Max Sum Plus Plus http://acm.hdu.edu.cn/showproblem.php?pid1024 1. 对于前n个数, 以v[n]为底取m段: 当nm时,Sum[m][n]Sum[m-1][n-1]v[n],第n个数独立成段; 当nm时, Sum[m][n]max{Sum[m-1][k],Sum[m][n-1]}v[n]; 其中,m-1kj,解释为,v[n]要么加在Sum[m][n-1],段数不变,要么独立成段接在前n-1个数取m-1段所能构成的最大值后面 2. 空间的优化: 通过状态方程可以看出,取m段时,只与取m-1段有关,所以用滚动数组来节省空间 30.FatMouse’s Speed http://acm.hdu.edu.cn/showproblem.php?pid1160 要求:体重严格递增,速度严格递减,原始顺序不定 按体重或者速度排序,即顺数固定后转化为最长上升子序列问题 Dp[i]表示为以第i项为底构成的最长子序列,Dp[i]max(dp[j])1,其中0ji , w[i]w[j]s[i]s[j] 用一个index数组构造最优解:记录每一项接在哪一项后面,最后用max找出最大的dp[0…n],dex记录下标,回溯输出即可 31.Cstructing Roads http://acm.hdu.edu.cn/showproblem.php?pid1025 以p或者r按升序排列以后,问题转化为最长上升子序列 题目数据量比较大,只能采取二分查找,n*log(n)的算法 用一个数组记录dp[]记录最长的子序列,len表示长度,如果a[i]dp[len], 则接在后面,len; 否则在dp[]中找到最大的j,满足dp[j]a[i],把a[i]接在dp[j]后面; 32.FatMouse Chees http://acm.hdu.edu.cn/showproblem.php?pid1078 Dp思想,用记忆化搜索;简单题,处理好边界; 33.To the Max http://acm.hdu.edu.cn/showproblem.php?pid1081 最大子矩阵 把多维转化为一维的最大连续子序列;(HDU1003) 34.龟兔赛跑http://acm.hdu.edu.cn/showproblem.php?pid2059 未总结 35.Employment Planning http://acm.hdu.edu.cn/showproblem.php?pid1158 状态表示: Dp[i][j]为前i个月的留j个人的最优解;Num[i]jMax{Num[i]}; jMax{Num[i]}之后无意义,无谓的浪费 记Max_nMax{Num[i]}; Dp[i-1]中的每一项都可能影响到Dp[i],即使Num[i-1]Num[i] 所以利用Dp[i-1]中的所有项去求Dp[i]; 对于Num[i]kMax_n, 当kj时, 招聘; 当kj时, 解雇 然后求出最小值 Dp[i][j]min{Dp[i-1][k…Max_n](招聘,解雇,工资); 36.Dividing http://acm.hdu.edu.cn/showproblem.php?pid1059 一维Dp Sum为偶数的时候判断Dp[sum/2]可不可达 37.Human Gene Factions http://acm.hdu.edu.cn/showproblem.php?pid1080 状态转移方程: f[i][j]Max(f[i-1][j-1]r[a[i]][b[j]], f[i][j-1]r[‘-‘][b[j]],f[i-1][j]r[a[i]][‘-‘]); 38.Doing Homework http://acm.hdu.edu.cn/showproblem.php?pid1074 这题用到位压缩; 那么任务所有的状态有2^n-1种 状态方程为:Dp[next]min{Dp[k]i的罚时} 其中,nextk(1i),k要取完满足条件的值 ki的奇偶性决定状态k 具体实现为: 对每种状态遍历n项任务,如果第i项没有完成,则计算出Dp[next]的最优解 39.Free DIY Tour http://acm.hdu.edu.cn/showproblem.php?pid1224 简单的数塔Dp,考察的是细节的处理; Dp[i]Max{Dp[j]}v[i] 其中j-i为通路; v[n1]有没有初始化,Dp数组有没有初始化 这题不能用想当然的”最长路”来解决,这好像是个NP问题 解决不了的 40.重温世界杯http://acm.hdu.edu.cn/showproblem.php?pid1422 这题的状态不难理解,状态表示为,如果上一个城市剩下的钱不为负,也就是没有被赶回杭电,则再考虑它对下一个城市的影响;如果上一个城市剩下的前加上当前城市的前大于当前城市的生活费,那么Dp[i]Dp[i-1]1; 值得注意的而是这题的数据为100000;不可能以每个城市为起点来一次Dp,时间复杂度为n^2;足已超时; 我是这样处理的,在保存的数据后面再接上1…n的数据,这样扫描一遍的复杂度为n;再加一个优化,当Dp[i]n时,也就是能全部游完所有城市的时候,直接break; 41.Pearls http://acm.hdu.edu.cn/showproblem.php?pid1300 Dp[i]min{Dp[j]V}, 0ji, V为第j1类珠宝到第i类全部以i类买入的价值; 42.Zipper http://acm.hdu.edu.cn/showproblem.php?pid1501 Dp[i][j] 43.Fast Food http://acm.hdu.edu.cn/showproblem.php?pid1227 这里需要一个常识:在i到j取一点使它到区间每一点的距离之和最小,这一点为(ij)/2用图形即可证明; Dp[i][j]max{Dp[i-1][k]cost[k1][j] 其中,(i-1)kj状态为前j个position建i个depots 44.Warcraft http://acm.hdu.edu.cn/showproblem.php?pid3008 比赛的时候这道DP卡到我网络中心停电!!! 卧槽~ 因为你没有回血效应,所以你挂掉的时间是一定的; 用Dp[i][j]表示第i秒剩余j个单位的MP时怪物所剩的血量; 注意必须是剩余,也就是说,初始化的时候,DP[0][100]100; 其他Dp[0]状态都不合法,因为没有开战的时候你的MP是满的 以前的Dp都是利用前面得到的最优解来解决,而这题的麻烦点是MP在攻击过后要自动恢复x个单位;用当前的状态的状态推下一状态,仔细想想也未尝不可;状态转移方程为: Dp[i1][j-sk[k].mpx]min(Dp[i1][j-sk[k].mpx],Dp[i][j]sk[k].at; 释放第K种技能,物理攻击可以看成是at1,mp0 的魔法; 45.Regular Words http://acm.hdu.edu.cn/showproblem.php?pid1502 F[a][b][c]F[a-1][b][c]F[a][b-1][c]F[a][b][c-1]; abc; 46.Advanced Fruits http://acm.hdu.edu.cn/showproblem.php?pid1503 最长公共子序列的加强版
