专题十二 基础DP1 题集

xiaoxiao2021-02-28  78

专题十二 基础DP1 DP具有的性质:最优子结构,子问题重叠,边界,子问题独立。 按照下面的步骤去考虑: 1、构造问题所对应的过程。 2、思考过程的最后一个步骤,看看有哪些选择情况。 3、找到最后一步的子问题,确保符合“子问题重叠”,把子问题中不相同的地方设置为参数。 4、使得子问题符合“最优子结构”。 5、找到边界,考虑边界的各种处理方式。 6、确保满足“子问题独立”,一般而言,如果我们是在多个子问题中选择一个作为实施方案,而不会同时实施多个方案,那么子问题就是独立的。 7、考虑如何做备忘录。 8、分析所需时间是否满足要求。 9、写出转移方程式。 A - Max Sum Plus Plus HDU - 1024 题意:在一组数取出m个不相交的区间,使区间和的总和最大。 题解:dp[i][j]表示取了第i个数,分为j个区间和的总和最大的值 dp[i][j] = max(dp[i-1][j]+a[i], max(dp[0……(i-1)][j-1])+a[i]); 因为dp[i][j]只和dp[][j-1]和dp[i-1][j]有关,所以只需一维数组即可 max(dp[0……(i-1)])可以在i-1层的时候处理出来,优化时间。 http://blog.csdn.net/qq_33199236/article/details/55808998 B - Ignatius and the Princess IV HDU - 1029 水题? C - Monkey and Banana HDU - 1069 叠放立方体,使其叠的高度最大。 dp[i] 表示以i为终点(或起点)的最大高度 1.在按底的长宽排序后,进行求最大子序列和 2.记忆化搜索,枚举以(1~n)开头的最大dp值 http://blog.csdn.net/qq_33199236/article/details/71270169 D - Doing Homework HDU - 1074 题意:作业超过时限,超过一天扣一分,给出n个作业及其时限和需要完成的时间,求最小扣分值和其路径 题解: 状态压缩dp,本应该要想到的。其N<=15,根据选没选压成二进制 因为题目要求最后方案如果多个情况以字典序排序,所以可以先将原数据先排序 然后我们发现递归时缺少了上一个状态的所用时间,我先预处理出来。 设这个状态为wi,上个状态为wj,这个状态和上个状态相差的那个作业的编号为id 那么 dp[wi] = dp[wj]+time[wj]+C[id]-D[id]。 http://blog.csdn.net/qq_33199236/article/details/56015043?locationNum=3&fps=1 E - Super Jumping! Jumping! Jumping! HDU - 1087 题意:最大递增子序列 题解: dp[i] 表示以i为终点的递增子序列最大值 dp[i] = max(dp[i],dp[j]+a[i]) {j < i} http://blog.csdn.net/qq_33199236/article/details/56024593 F - Piggy-Bank HDU - 1114 题意:装满背包,但要求价值最低的完全背包 题解: dp[i][j] 表示在背包大小为j中装前i个物品最优的价值 http://blog.csdn.net/qq_33199236/article/details/56025506 G - 免费馅饼 HDU - 1176 题意:在一个坐标轴上,最初处在5上,给出一些点在一些时间能得到1个馅饼,每秒能移动一格,问最大能得到的馅饼个数。 题解:数塔问题 1. 预处理mp[i][j]表示在第i秒第j处能得到几个馅饼 dp[i][j] 表示在前i秒,人在j处能得到最大馅饼数 dp[i][j] = max(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+mp[i][j]; 2. dp[i][j] 表示在从i秒开始,人在j处能得到最大馅饼数 dp[i][j] = max(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1])+mp[i][j]; http://blog.csdn.net/qq_33199236/article/details/56047317 H - Tickets HDU - 1260 题意: n个人在买电影票,可以两个相邻的一起买,也可以单独买,给出分别需要的时间,问需要的最短时间 题解: dp[i] 代表前i人的最小花费时间 http://blog.csdn.net/qq_33199236/article/details/56671330 I - 最少拦截系统 HDU - 1257 题解: dp[i] 代表第i个人使用的拦截导弹系统 http://blog.csdn.net/qq_33199236/article/details/56675683 J - FatMouse's Speed HDU - 1160 题意:给出n组数据,要求选择数据,证明越胖跑的越慢(即找个最长的体重严格递增而速度严格递减的数据)。 题解: LIS题 先按体重排序下,然后就是LIS找最长递减就好了 记录路径: 1. 记录终点,最后倒推回去,下面代码用的这种方式 2. 直接在过程中记录:dp[i].pre = j;(或者用其他数组记录也可) http://blog.csdn.net/qq_33199236/article/details/56677891 K - Jury Compromise POJ - 1015 题意: n组D[j],P[j]数字,选择m组使选择的D[j]和与P[j]和差最小,如果和差相等,选择D[j]和与P[j]和的总和最大的。 题解: dp[i][j] 代表选第i个,选择的D[]和与P[]和差为j的 最大总和。 path[i][j] 记录前i个选择的组。 ca[i] = D[i]-P[i]; he[i] = D[i]+P[i]; 如果选择的前i组和差无法达到j,那么dp[i][j] = -1; if(k 前面有路径 && k 在前面的路径上没有出现)     dp[i][j+ca[k]] = max(dp[i][j+ca[k]],dp[i-1][j]+he[k]); j 的原有范围应该是-20*m~20*m , 将其范围加上20*m 变成 0~40*m; http://blog.csdn.net/qq_33199236/article/details/59054986 L - Common Subsequence POJ - 1458 题意:求最长公共子序列 题解: LCS题 具体的思路我在其他写51nod 1006 题解写过。 简单的来讲: dp[i][j] 表示在第一序列的前i个和第二序列的前j个的最长公共子序列长度 dp[i][j] = a[i] == b[j] ? dp[i-1][j-1]+1 : max(dp[i-1][j],dp[i][j-1]); http://blog.csdn.net/qq_33199236/article/details/56678732 M - Help Jimmy POJ - 1661 题解: 首先无疑的肯定要按高度进行从高到低排序,肯定有解,那么高度肯定加上去,再加上最少的横向走的时间 应该有两种决策,向左跳,向右跳 dp[i][0] 代表以i左边为起点向左跳到达地面的距离,dp[i][1] 代表以i右边为起点向右跳到达地面的距离 如果i平台左能跳到j平台: dp[i][0] = min(dp[j][0]+a[i].l-a[j].l ,dp[j][1]+a[j].r-a[i].l) +a[i].h-a[j].h; 同理i平台右边。 http://blog.csdn.net/qq_33199236/article/details/56680834 N - Longest Ordered Subsequence POJ - 2533 题解:裸LIS http://blog.csdn.net/qq_33199236/article/details/56681546 O - Treats for the Cows POJ - 3186 题意:给你一组数,可以选择取最前面的数和最后面的数,第i次取到这个数, 就将总数加上(i*取的数),使总数最大。 题解:dp[i][j] 代表从i取到j的最大总数 dp[i][j] = max(dp[i+1][j]+a[i]*(n+i-j) , dp[i][j-1]+a[j]*(n+i-j)); http://blog.csdn.net/qq_33199236/article/details/71270845 P - FatMouse and Cheese HDU - 1078 题意: 从(0,0)出发,每次最多走k格,但每次只能往 值比它现在在的值大的格子走。 题解:dp[i][j] 代表走到(i,j)的最大总值。 dp[i][j] = max(dp[prei][prej]+mp[i][j]){i,j 是 prei,prej能走到的格子} 贡献1T,1Wa,注意题意走K步是只能笔直走K步,导致T。 我以为我nextx是不断更新的,没乘j,导致wa。 http://blog.csdn.net/qq_33199236/article/details/58132282?locationNum=1&fps=1 Q - Phalanx HDU - 2859 题意:问矩阵最大对称矩阵(按左下角到右上角对称)的对角线长度 题解: 设mp[i][j] 代表处于(i,j)的上面与右边字符对称的最长长度 dp[i][j] 代表走到(i,j)的最大对称矩阵的对角线长度 if(mp[i][j] > dp[i-1][j+1])     dp[i][j] = dp[i-1][j+1]+1; else     dp[i][j] = mp[i][j]; 因为dp的递归方程只与i-1有关,可以化成一维数组 http://blog.csdn.net/qq_33199236/article/details/58221777 R - Milking Time POJ - 3616 题意: 在N小时内,有M个可以得到的牛奶,在相应的时间段得到相应的牛奶,在一时间只能处理一个, 而且每次得到后要休息R时间,才能进行下一次。问最大能得到的牛奶总量。 题解:首先每个时间段都在N内,那其实就是求在m个选择几个得到最大。 先将结束的时间均加上R,就能处理R的问题了吧。 然后就类似叠塔问题了,排序+LIS吧 http://blog.csdn.net/qq_33199236/article/details/71271026 S - Making the Grade POJ - 3666 题意: 给出n个数字组成序列a,然后再找到一个序列b,从1至n,abs(a[i]-b[i])的总和最小, 其中序列b是非严格单调序列,要么是要么是非递减序列,要么是非递增序列。 题解:分别求非严格递减和非严格递减的答案,取最小值 怎么求? 非严格递增: 如果数组数字需要改变,那么往目前数组最大的数字变 将数组排序存于c[]; dp[i][j]代表取第i个数,现在集合最后的数是排序后的数组的第j个 dp[i][j] = min(dp[i-1][k])(1<=k<=j)+abs(a[i]-c[j]) http://blog.csdn.net/qq_33199236/article/details/58320195
转载请注明原文地址: https://www.6miu.com/read-55963.html

最新回复(0)