关于最优子结构的正确性，状态的有穷性，状态转移的正确性！以及动态规划的出发 点，常用的模型和转移方程，仔细看一下！网上找的一些题目思路和转移方程，不妨看一 下！体会动态规划的思想！ Robberies 背包;第一次做的时候把概率当做背包(放大 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 块大洋肯定不被抓嘛)最大报销额 又一个背包问题,对于每张发票,要么报销,要么不报销,0-1 背包,张数即为背包;转移方程:f[j]=max(f[j],f[j-1]+v[i]);恶心地方:有这样的输入数据 3 A:100 A:200 A:300最大连续子序列 sum 同上,最大连续子序列 Largest Rectangle 其中,j=height[i];找 j,k 成为 关键,一般方法肯定超时,利用动态规划,如果它左边高度大于等于它本身,那么它左边的左边 界一定满足这个性质,再从这个边界的左边迭代下去for(i=1;i=a[i])l[i]=l[l[i]-1];}for(i=n;i>=1;i--){while(a[r[i]+1]>=a[i])r[i]=r[r[i]+1];}City Game 的加强版,把 2 维转换化成以每一行底,组成的最大面积;(注意处理连续与间断的情 况);Bone Collector 简单 0-1 背包,状态方程:f[j]=max(f[j],f[j-v[i]]+w[i])Super Jumping 最大递增子段和,状态方程:sum[j]=max{sum[i]}+a[j]; 其中,0=v[i] 数塔 免费馅饼 Need A Offer 0-1 背包,题目要求的是至少收到一份 Offer 的最大概率,我们得到得不到的最小概 率即可,状态转移方程:f[j]=min(f[j],f[j-v[i]]*w[i]);其中,w[i]表示得不到的概率,(1-f[j])为花费 j 元得到 Offer 的最大概率 FATE 二维完全背包,第二层跟第三层的要顺序循环;(0-1 背包逆序循环);状态可理解为,在背包 属性为 {m(忍耐度), s(杀怪个数)} 里最多能得到的经验值,之前的背包牺牲体积,这个背包牺 牲忍耐度跟个数注意: 最后扫的时候 外层循环为忍耐度,内层循环为杀怪个数,因为题目要求出剩余忍 耐度最大,没有约束杀怪个数,一旦找到经验加满的即为最优解;状态转移方程为: f[j][k]=max(f[j][k],f[j-v[i]][k-1]+w[i]); w[i]表示杀死第 i 个怪所得的经 验值,v[i]表示消耗的忍耐度How To Type 用两个 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~ Coins HDU1171 Big Event In HDU,一维 DP,可达可不达 Beans 横竖分别求一下不连续的最大子段和;状态方程: Sum[i]=max(sum[j])+a[i];其中,0=height[i]的个数即可,这里用 hash+滚动,先 求出 height[i]出现的次数,然后逆序扫一遍 hash[i]+=hash[i+1]; 最少拦截系统 DP;if(v[i]>max{dp[j]}) (0j*2 时,Dp[i][j] = min(Dp[i-1][j],Dp[i-2][j-1]+(w[j]-w[j-1])^2) ★ Humble Numbers 如果一个数是 Humble Number,那么它的 2 倍,3 倍,5 倍,7 倍仍然是 Humble Number定义 F[i]为第 i 个 Humble NumberF[n]=min(2*f[i],3*f[j],5*f[k],7*f[L]), i,j,k,L 在被选择后相互移动(通过此题理解到数组有序特性) ★ Doing Homework Again 这题为贪心,经典题;切题角度,对于每个任务要么在截至日期前完成要么被扣分;所以考虑每个人物的完成情 况即可;由于每天只能完成一个任务,所以优先考虑分值较大的任务,看看该任务能不能完成, 只要能完成,即使提前完成,占了其他任务的完成日期也没关系,因为当前任务的分值最大嘛, 而对于能完成的任务能拖多久就拖多久,以便腾出更多时间完成其他任务; How Many Ways 两种 D 法,一是对于当前的点,那些点可达;二是当前点可达那些点;明显第二种方法高,因为第一种方法有一些没必要的尝试;Dp[i][j]+=Dp[ii][jj]; (map[ii][jj]>=两点的曼哈顿距离)值得优化的地方,每两点的曼哈顿距离可能不止求一次,所以预处理一下直接读取 珍惜现在 感恩生活 每个物品最多可取 n 件,多重背包;利用二进制思想,把每种物品转化为几件物品,然后就成为了 0-1 背包 Piggy-Bank 完全背包;常规背包是求最大值,这题求最小值;只需要修改一下初始化,f[0]=0,其他赋值为+∞即可;状态转移方程:f[i][V]=max{f[i-1][V],f[i-1][V-k*v[i]]+k*w[i]},其中 0m 时, Sum[m][n]=max{Sum[m-1][k],Sum[m][n-1]}+v[n]; 其中,m-1w[j]否则在 dp[]中找到最大的 j,满足 dp[j]Max{Num[i]}之后无意义,无谓的浪费 记 Max_n=Max{Num[i]};Dp[i-1]中的每一项都可能影响到 Dp[i],即使 Num[i-1]j 时, 解雇 然后求出最小值Dp[i][j]=min{Dp[i-1][k…Max_n]+(招聘,解雇,工资); Dividing 一维 Dp Sum 为偶数的时候判断 Dp[sum/2]可不可达 Human Gene Factions 状态转移方程: 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]][‘-‘]);★ Doing Homework 这题用到位压缩;那么任务所有的状态有 2^n-1 种状态方程为:Dp[next]=min{Dp[k]+i 的罚时} 其中,next=k+(1>i 的奇偶性决定状态 k 具体实现为: 对每种状态遍历 n 项任务,如果第 i 项没有完成,则计算出 Dp[next]的最优解 Free DIY Tour 简单的数塔 Dp,考察的是细节的处理;Dp[i]=Max{Dp[j]}+v[i] 其中 j->i 为通路;v[n+1]有没有初始化,Dp 数组有没有初始化这题不能用想当然的”最长路”来解决,这好像是个 NP 问题 解决不了的重温世界杯 这题的状态不难理解,状态表示为,如果上一个城市剩下的钱不为负,也就是没有被赶回杭电, 则再考虑它对下一个城市的影响;如果上一个城市剩下的前加上当前城市的前大于当前城市 的生活费,那么 Dp[i]=Dp[i-1]+1; 值得注意的而是这题的数据为 100000;不可能以每个城市为起点来一次 Dp,时间复杂度为 n^2;足已超时; 我是这样处理的,在保存。