《动态规划方法例题讲述》由会员分享,可在线阅读,更多相关《动态规划方法例题讲述(50页珍藏版)》请在金锄头文库上搜索。
1、动态规划方法例题 最长上升子序列问题 一个序列有N个数:A1,A2,AN,求 出最长上升子序列的长度(LIS:longest increasing subsequence)。 例如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的 一些上升子序列,如(1, 7), (3, 5, 9) , (3, 4, 8)等等。这些子序列中最长的长度是4,比 如子序列(1, 3, 5, 9) ,(1, 3, 5, 8)和(1, 3, 4, 8). 分析 假如我们考虑求A1,A2,Ai的最长上升 子序列的长度,其中ilen) len = di; 序列变化 求最长非降子序列(longest non-de
2、creasing subsequence),与此问题近似。只需要将上述条 件Ajlen) len = di; 例2 乘积最大 问题描述 设有一个长度N的数字串,要求选手使用K个乘号将它分 成K+1个部分,找出一种分法,使得这K+1个部分的乘积 能够为最大。 例子:有一个数字串: 312,当N=3,K=1时会有以下两种 分法: 1)3*12=36 2)31*2=62 这时,符合题目要求的结果是: 31*2=62 现在,请你设计一个程序,求得正确的答案。 (蓝桥网站题目编号:ALGO-17 VIP试题2013-11-07 ) 输入输出样例 输入: 输入中有若干组测试数据,每组测试数据有两行:第 一
3、行共有2个自然数T,K (6=vi)*/ 例5 装箱问题 有一个箱子容量为V(正整数,0V20000),同时 有n个物品(0n30),每个物品有一个体积(正整 数)。 要求n个物品中,任取若干个装入箱内,使箱子的剩余 空间为最小。 输入格式 第一行为一个整数,表示箱子容量; 第二行为一个整数,表示有n个物品; 接下来n行,每行一个整数表示这n个物品的各自体积。 输出格式 一个整数,表示箱子剩余空间。 蓝桥网编号:ALGO-21 VIP试题 2013-11-07 输入输出样例 样例输入 24 6 8 3 12 7 9 7 样例输出 0 分析 这是一个变形的背包问题,最优目标是:使 箱子的剩余空间
4、为最小。可转换成物品占 据的容量最大。 用Fi,j表示容量为j的箱子装入前i个物品后, 物品占据的容量。则状态转移方程为: Fi,j= maxFi-1,j-ai+ai,Fi-1,j 其中ai表示第i个物品的体积。 主要代码段 dp0=0;/注意这是关键 for(i=0;i=a;j-) dpj=max(dpj,dpj-a+a); 收集苹果:二维的DP问题 平面上有NM个格子,每个格子中放着一 定数量的苹果。你从左上角的格子开始, 每一步只能向下走或是向右走,每次走到 一个格子上就把格子里的苹果收集起来, 这样下去,你最多能收集到多少个苹果。 我们必须注意到的一点是,到达一个格子 的方式最多只有两
5、种:从左边来的(除了第 一列)和从上边来的(除了第一行)。 分析 因此为了求出到达当 前格子后最多能收集 到多少个苹果,我们 就要先去考察那些能 到达当前这个格子(i,j) 之前的格子,到达它 们最多能收集到多少 个苹果。 (i-1,j) (i,j-1)(i,j) Ai,j 状态和状态转移方程 状态Sij表示我们走到(i, j)这个格子时,最 多能收集到多少个苹果。 那么,状态转移方程如下: Sij=Aij + max(Si-1j, if i0 ; Sij-1, if j0) 其中i代表行,j代表列,下标均从0开始; Aij代表格子(i, j)处的苹果数量。 例6 传纸条 小渊和小轩是好朋友也
6、是同班同学,他们在一起总有谈不完的话题。 一次素质拓展活动中,班上同学安排做成一个m行n列的矩阵,而小渊 和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸 运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对 方手里,小渊坐在矩阵的左上角,坐标(1,1),小轩坐在矩阵的右下角, 坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递,从小轩 传给小渊的纸条只可以向上或者向左传递。 在活动进行中,小渊希望给小轩传递一张纸条,同时希望小轩给他回 复。班里每个同学都可以帮他们传递,但只会帮他们一次,也就是说如 果此人在小渊递给小轩纸条的时候帮忙,那么在小轩递给小渊的时候就
7、 不会再帮忙。反之亦然。 还有一件事情需要注意,全班每个同学愿意帮忙的好感度有高有低( 注意:小渊和小轩的好心程度没有定义,输入时用0表示),可以用一 个0-100的自然数来表示,数越大表示越好心。小渊和小轩希望尽可能 找好心程度高的同学来帮忙传纸条,即找到来回两条传递路径,使得这 两条路径上同学的好心程度之和最大。现在,请你帮助小渊和小轩找到 这样的两条路径。 蓝桥网题目编号:ALGO-36VIP试题2013-11-08 输入输出格式 输入格式 输入第一行有2个用空格隔开的整数m和n,表 示班里有m行n列(1=m,n=50)。 接下来的m行是一个m*n的矩阵,矩阵中第i 行j列的整数表示坐在
8、第i行j列的学生的好心程度 。每行的n个整数之间用空格隔开。 输出格式 输出一行,包含一个整数,表示来回两条路上 参与传递纸条的学生的好心程度之和的最大值。 样例输入输出 样例输入 3 3 0 3 9 2 8 5 5 7 0 样例输出 34 数据规模和约定 30%的数据满足:1=m,n=10 100%的数据满足:1=m,n=50 传纸条(甩干后) 小渊坐在矩阵的左上角,坐标(1,1),小轩坐在矩 阵的右下角,坐标(m,n)。从小渊传到小轩的纸条 只可以向下或者向右传递,从小轩传给小渊的纸 条只可以向上或者向左传递。 班里每个同学都可以帮他们传递,但只会帮他们 一次。 每个同学愿意帮忙的好感度有
9、高有低,可以用一 个0-100的自然数来表示,数越大表示越好心。 小渊和小轩希望尽可能找好心程度高的同学来帮 忙传纸条,即找到来回两条传递路径,使得这两 条路径上同学的好心程度之和最大。现在,请你 帮助小渊和小轩找到这样的两条路径。 1=m,n=50 贪心 很容易想到一个算法: 求出1个纸条从(1,1)到(M,N)的路线最大值. 删除路径上的点值 再求出1个纸条从(M,N) 到(1,1)的路线最大值. 统计两次和 上述算法很容易找出反例,如下图。 第1次找最优值传递后,导致第2次无法传递。 分析 贪心算法错误,因此我们需要同时考虑两个纸条的传递。 由于小渊和小轩的路径可逆,因此,尽管出发点不同
10、,但 都可以看成同时从(1,1)出发到达(M,N)点。 设f(i1,j1,i2,j2)表示纸条1到达(i1,j1)位置,纸条2到达(i2,j2)位 置的最优值。则有, 其中 (i1,j1)!= (i2,j2) 1=i1, i2=M, 1=j1 , j2=N 时间复杂度O(N2M2) 地宫取宝 X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子 放一件宝贝。每个宝贝贴着价值标签。 地宫的入口在左上角,出口在右下角。 小明被带到地宫的入口,国王要求他只能向右或向下行 走。 走过某个格子时,如果那个格子中的宝贝价值比小明手 中任意宝贝价值都大,小明就可以拿起它(当然,也可以 不拿)。 当
11、小明走到出口时,如果他手中的宝贝恰好是k件,则 这些宝贝就可以送给小明。 请你帮小明算一算,在给定的局面下,他有多少种不同 的行动方案能获得这k件宝贝。 蓝桥网编号:PREV-28 地宫取宝 普通试题2014-03-25 输入输出格式 输入格式 输入一行3个整数,用空格分开:n m k (1=n,m=50, 1=k=12) 接下来有 n 行数据,每行有 m 个整数 Ci (0=Ci=12)代表这个格子上的宝物的价值 输出格式 要求输出一个整数,表示正好取k个宝贝 的行动方案数。该数字可能很大,输出它 对 1000000007 取模的结果。 输入输出样例 样例输入 2 2 2 1 2 2 1 样例输出 2 样例输入 2 3 2 1 2 3 2 1 5 样例输出 14