一、动态规划的思想 1.先上一波官方解读提提神: 动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。  动态规划常常适用于有重叠子问题和最优子结构性质的问题。 官方术语太多?不能理解?what are you fucking say???? :) 往...

杭电2159--FATE

动态规划

  

2019-07-01 12:52:57

题目描述: 解析: 这道题是很明显的完全背包问题,所不同的是在背包容量限制的基础上限定了最多可以拿取的物品数量。最开始做的时候不知道新增的限制条件怎么使用,参考了网上的代码,写一下思路: 既然新增了一条限制,也就是要保证拿取的数量要小于限制的数量,那么可以对原有的数组新增加一个维度: 状态设计:dp[z][j]表示杀z个怪且花费不超过j的情况下得到的最大经验值 状态转移方程:dp[z][j]=ma...

杭电2844--Coins

动态规划

  

2019-07-06 23:00:50

题目描述: 解析: 知道这是多重背包问题,但是初做这道题时我还是不知道用什么作为背包容量,而通过分析这道题发现,题目所求是价值不超过m的方案的个数。对于(1–m)内的任意一个价值,如果最佳方案dp[i]达到了这个值,那么就可以说存在这种方案。因此建立如下转移方程: dp[i][j]=max{dp[i-1][j],dp[i-1][j-v[i]]+v[i]} 其中dp[i][j]表示的是装...

动态规划(一)

动态规划

  

2019-07-07 12:31:47

动态规划(一) 算法导论动态规划——钢条切割 **Serling公司购买长钢条,将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…,单位为美元)。钢条的长度均为整英寸。图15-1给出了一个价格表的样例。 钢条切割问题是这样的:给定一段长度为n英寸的...

杭电1087--Super Jumping

动态规划

  

2019-07-08 07:27:01

题目描述: 解析: 很水的一道题,就是把最长递增子序列的长度变为了最长递增子序列的和,让dp[i]来表示以a[i]结尾的最长子序列的和就好了。 递推公式: dp[i]=max{dp[i],dp[j]+a[i]} 不过需要注意的一点是,此处外层循环的下标就要从1而不是2开始了,因为也需要计算dp[1]的值。 代码:...

杭电1003--Max Sum

动态规划

  

2019-07-08 08:44:46

题目描述: 解析: 这道题求的是连续子序列的和的最大值,联想到最长递增子序列,不妨用动态规划的想法去做。 我们假设原始序列的元素为a[n],dp[i]为以第i个元素为结尾的子序列的最大值,那么通过一趟遍历,依次比较以第i个元素为结尾的子序列的最大值即可。 举例说明,一个序列如下: 通过分析不难发现,以第i个元素为结尾的子序列的最大值存在两种情况: (1)既然是连续的子序列,那么如果以a[i-1]结...

72. Edit Distance

动态规划

  

2019-07-08 09:51:51

给你两个单词word1,word2,使用最少的次数将word1转化为word2。你只可以进行下面三种操作: 1、插入一个字符  2、删除一个字符  3、替换到一个字符。  递归求解(记忆化搜索)  ...

原博客地址: https://www.cnblogs.com/brucemengbm/p/6875340.html 五大经常使用算法 之 动态规划法 一、基本概念     动态规划过程是:每次决策依赖于当前状态。又随即引起状态的转移。 一个决策序列就是在变化的状态中产生出来的,所以,这样的多阶段最优化决策解决这个问题的过程就称为动态规划。   &n...

洛谷传送门 BZOJ传送门 题目描述 国际象棋是世界上最古老的博弈游戏之一,和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想,棋盘是一个8×88×8大小的黑白相间的方阵,对应八八六十四卦,黑白对应阴阳。 而我们的主人公小Q,正是国际象棋的狂热爱好者。作为一个顶尖高手,他已不满足于普通的棋盘与规则,于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。...

杭电2059--龟兔赛跑

动态规划

  

2019-07-16 16:25:47

题目描述: 解析: 使用动态规划思想建立模型,开始以为自己对动态规划已经很熟练了,做了这道题才发现,呵呵~还是得练! 废话不多说,这道题的思想如下: 想要求乌龟与兔子谁先到达终点,其实就是拿乌龟到达终点的最快速度与兔子的相比,因此我们设乌龟到达某一点最快的时间为dp[n],对于每过一个点,存在充电与不充电两种情况,因此我最初的想法是比较充电与不充电这两种情况的最短时间,作为dp[i]。然而真正写完...

Description 自从 Y 君退役之后,她就迷上了吃鸡,于是她决定出一道吃鸡的题。 Y 君将地图上的所有地点标号为 1 到 n,地图中有 n − 1 条双向道路连接这些点,通过一条 双向道路需要一定时间,保证从任意一个点可以通过道路到达地图上的所有点。 有些点上可能有资源,Y 君到达一个有资源的点后,可以选择获取资源来使自己的武力值增 加 wi,也可以选择不获取资源。如果 Y 君...

传送门:最佳加法表达式 11:最佳加法表达式 描述 给定n个1到9的数字,要求在数字之间摆放m个加号(加号两边必须有数字),使得所得到的加法表达式的值最小,并输出该值。例如,在1234中摆放1个加号,最好的摆法就是12+34,和为36 输入 有不超过15组数据 每组数据两行。第一行是整数m,表示有m个加号要放( 0<=m<=50) 第二行是若干个数字。数字总数n不超过50,且 m &l...

题目链接 题意: 每个系统由多个设备组成,每个设备由多个厂家可以提供,厂家提供不同的设备带宽和价格,选择厂家提供的设备,最后使得整个系统的总B(最小带宽)/总P(价格)最大 题解: 二维动态规划,前i个设备带宽为j时最小的价格 代码:  ...