• 1. 动态规划
  • 2. F(n) = 1 if n = 0 or 1 F(n-1) + F(n-2) if n > 1n012345678910F(n)1123581321345589斐波纳契数列F(n)2
  • 3. 递归 vs 动态规划递归版本: F(n) 1 if n=0 or n=1 then 2 return 1 3 else 4 return F(n-1) + F(n-2)动态规划: F(n) 1 A[0] = A[1] ← 1 2 for i ← 2 to n do 3 A[i] ← A[i-1] + A[i-2] 4 return A[n]太慢!有效率! 算法复杂度是 O(n)3
  • 4. 方法概要构造一个公式,它表示一个问题的解是与它的子问题的 解相关的公式. E.g. F(n) = F(n-1) + F(n-2). 为这些子问题做索引 ,以便它们能够在表中更好的存储与检索 (i.e., 数组array【】) 以自底向上的方法来填写这表格; 首先填写最小子问题的解. 这就保证了当我们解决一个特殊的子问题时, 可以利用比它更小的所有可利用的 子问题的解.由于历史原因, 我们称这种方法为: 动态规划. 在上世纪40年代末 (计算机普及很少时), 这些规划设计是与”列表“方法相关的.4
  • 5. 动态规划算法算法思想 将待求解的问题分解成若干个子问题,并存储子问题的解而避免计算重复的子问题,并由子问题的解得到原问题的解。 动态规划算法通常用于求解具有某种最优性质的问题。 动态规划算法的基本要素: 最优子结构性质和重叠子问题。原理5
  • 6. 最优子结构性质:问题的最优解包含着它的子问题的最优解。即不管前面的策略如何,此后的决策必须是基于当前状态(由上一次决策产生)的最优决策。 重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些问题被反复计算多次。对每个子问题只解一次,然后将其解保存起来,以后再遇到同样的问题时就可以直接引用,不必重新求解。原理6
  • 7. 动态规划解决问题的基本特征1. 动态规划一般解决最值(最优,最大,最小,最长……)问题;2. 动态规划解决的问题一般是离散的,可以分解(划分阶段)的;3. 动态规划解决的问题必须包含最优子结构,即可以由(n-1)的最优推导出n的最优原理7
  • 8. 动态规划算法的4个步骤: 1. 刻画最优解的结构特性. (一维,二维,三维数组) 2. 递归的定义最优解. (状态转移方程) 3. 以自底向上的方法来计算最优解. 4. 从计算得到的解来构造一个最优解. 解决问题的基本步骤原理8
  • 9. 实例例题一. 斐波纳契数列F(n)F(n) = 1 if n = 0 or 1 F(n-1) + F(n-2) if n > 1步骤1:用F(n)表示在斐波纳契数列中第n个数的值;步骤2:状态转移方程:步骤3:以自底向上的方法来计算最优解n012345678910F(n)1123581321345589步骤4:在数组中分析构造出问题的解;9
  • 10. 例题二. 输入n,求出n!F(n) = 1 if n = 0 or 1 F(n-1) *n if n > 1步骤1:用F(n)表示n!的值;步骤2:状态转移方程:步骤3:以自底向上的方法来计算最优解n012345678910F(n)112624120720实例10
  • 11. 例题三:排队买票问题 一场演唱会即将举行。现有n个歌迷排队买票,一个人买一张,而售票处规定,一个人每次最多只能买两张票。假设第i位歌迷买一张票需要时间Ti(1≤i≤n),队伍中相邻的两位歌迷(第j个人和第j+1个人)也可以由其中一个人买两张票,而另一位就可以不用排队了,则这两位歌迷买两张票的时间变为Rj,假如Rj
  • 12. 分析:如果前i个人买票的最优买票方式一确定,比如第i-1个人买一张票,则前i-1个人的买票方式也一定是最优的。即问题的最优解包含子问题的最优解。12345i…in-1nn-2…步骤1:用F(i)表示前i个人买票的最优方式,即所需最短时间;现在要决定F(i)需要考虑两种情况: (1)第i个人的票自己买 (2)第i个人的票由第i-1个人买 步骤2:状态转移方程:min步骤3:以自底向上的方法来计算最优解12
  • 13. 程序的实现BuyTicks(T, R) 1 n ← length[T] 2 f[0] ← 0 3 f[1] ← T[1] 4 for i ← 2 to n do 5 f[i] ← f[i-2]+R[i-1] 6 if f[i] > f[i-1]+T[i] then 7 f[i] ← f[i-1]+T[i] 8 return f13
  • 14. 实例例题四:求最长不降子序列1.问题描述 设有一个正整数的序列:b1,b2,…,bn,对于下标i1
  • 15. 拓展1: 拦截导弹 (vijos1303)某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 样例: INPUT OUTPUT 389 207 155 300 299 170 158 65 6(最多能拦截的导弹数) 2(要拦截所有导弹最少要配备的系统数)15
  • 16. 拓展2:低价购买 “低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者,你必须遵循以下的问题建议:“低价购买;再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下,求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(216范围内的正整数),你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买;再低价购买”的原则。写一个程序计算最大购买次数。 这里是某支股票的价格清单: 日期 1 2 3 4 5 6 7 8 9 10 11 12 价格 68 69 54 64 68 64 70 67 78 62 98 87 最优秀的投资者可以购买最多4次股票,可行方案中的一种是: 日期 2 5 6 10 价格 69 68 64 62 输入 第1行: N (1 <= N <= 5000),股票发行天数 第2行: N个数,是每天的股票价格。 输出 输出文件仅一行包含两个数:最大购买次数和拥有最大购买次数的方案数(<=231)当二种方案“看起来一样”时(就是说它们构成的价格队列一样的时候),这2种方案被认为是相同的。16
  • 17. 拓展3:合唱队形 (vijis1098) N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。   合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK,  则他们的身高满足T1<...Ti+1>…>TK(1<=i<=K)。   你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。 输入的第一行是一个整数N(2<=N<=100),表示同学的总数。第一行有n个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。 输出包括一行,这一行只包含一个整数,就是最少需要几位同学出列。 样例输入 8 186 186 150 200 160 130 197 220样例输出: 417
  • 18. 例题五. 马拦过河卒实例[问题描述]:   如图,A 点有一个过河卒,需要走到目标 B 点。卒行走规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的马(如上图的C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点(图中的P1,P2 … P8 和 C)。卒不能通过对方马的控制点。 棋盘用坐标表示,A 点(0,0)、B 点(n,m)(n,m 为不超过 20 的整数,并由键盘输入),同样马的位置坐标是需要给出的(约定: C<>A,同时C<>B)。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。 [输入]: 键盘输入 B点的坐标(n,m)以及对方马的坐标(X,Y){不用盘错} [输出]:   屏幕输出     一个整数(路径的条数)。 [输入输出样例]:   输入:    6 6 3 2   输出:    17 18
  • 19. 步骤1:用F(X,Y)表示到棋盘上每个阶段(X,Y)的路径条数;步骤2:状态转移方程:步骤3:以自底向上的方法来计算最优解分析:阶段:棋盘上的每个可走的点; 每个阶段的求解;F(X,Y)= F (X-1,Y)+ F(X, Y-1) 其中,F(0,0 )=1 F (0,Y)=1 F (X,0)=119
  • 20. 例题六:数字三角形问题1.问题描述 设有一个三角形的数塔,顶点结点称为根结点,每个结点有一个整数数值。从顶点出发,可以向左走,也可以向右走。如图10一1所示。 问题:当三角形数塔给出之后,找出一条从第一层到达底层的路径,使路径的值最大。若这样的路径存在多条,任意给出一条即可。 20
  • 21. 步骤1二维数组 D(X,y)描述问题,D(X,y)表示从顶层到达第X层第y个位置的最小路径得分。步骤2:状态转移方程阶段分析:D(1,1)=13 到第x层的第y个位置有两种可能,要么走右分支 得到,要么走左分支得到。 D(X,y)=min{D(X-1,y),D(X-1,y-1}+a(X,y) D(1,1)=a(1,1) 21
  • 22. 拓展:栈(vijos 1122) 【问题背景】栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一个元素进栈)。宁宁考虑的是这样一个问题:一个操作数序列,从1,2,一直到n(图示为1到3的情况),栈A的深度大于n。 现在可以进行两种操作, 1.将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的push操作) 2. 将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的pop操作) 22
  • 23. 使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由1 2 3生成序列2 3 1的过程。(原始状态如上图所示) 1 2 3 1 2 31 3 2 2 2 3 2 3 123
  • 24. 你的程序将对给定的n,计算并输出由操作数序列1,2,…,n经过操作可能得到的输出序列的总数。 【输入格式】 输入文件只含一个整数n(1≤n≤18) 【输出格式】 输出文件只有一行,即可能输出序列的总数目 【输入样例】 3 【输出样例】 524
  • 25. 例题七:最长公共子序列一个给定序列的子序列是在该序列中删去若干元素后得到的序列。 给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。 最长公共子序列:公共子序列中长度最长的子序列。 最长公共子序列问题 给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…, yn},找出X和Y的一个最长公共子序列。 例如: X = (A, B, C, B, D, A, B) X的子序列: 所有X的子集(集合中元素按原来在X中的顺序排列) (A, B, D), (B, C, D, B), 等等.25
  • 26. 例子X = (A, B, C, B, D, A, B) X = (A, B, C, B, D, A, B) Y = (B, D, C, A, B, A) Y = (B, D, C, A, B, A) (B, C, B, A)和(B, D, A, B)都是X和Y 的最长公共子序列(长度为4) 但是,(B, C, A)就不是X和Y的最长公共子序列26
  • 27. 穷举法对于每一个Xm的子序列,验证它是否是Yn的子序列. Xm有2m个子序列 每个子序列需要o(n)的时间来验证它是否是Yn的子序列. 从Yn的第一个字母开始扫描下去,如果不是则从第二个开始 运行时间: o(n2m)27
  • 28. 给定一个序列Xm = (x1, x2, …, xm),我们定义Xm的第i个前缀为: Xi = ( x1, x2, …, xi ) i = 0, 1, 2, …, m c[i, j]为序列Xi = (x1, x2, …, xi)和Yj = (y1, y2, …, yj)的最长公共子序列的长度. 分析:最优子结构性质: 设序列Xm={x1,x2,…,xm}和Yn={y1,y2,…,yn}的一个最长公共子序列为Zk={z1,z2,…,zk},则 1.若xm=yn,则zk=xm=yn,且Zk-1是Xm-1和Yn-1的最长公共子序列。 2.若xm≠yn,且zk≠xm,则Zk是Xm-1和Yn的最长公共子序列。 3.若xm≠yn,且zk≠ yn ,则Zk是Xm和Yn-1的最长公共子序列。步骤1步骤228
  • 29. 状态转移方程00000000000yj:xmy1y2ynx1x2xii012nm120firstsecond步骤329
  • 30. 附加信息00000000000yj:DACFABxiji012nm120矩阵 b[i, j]: 它告诉我们要获得最优结果应该如何选择 如果 xi = yj b[i, j] = 1 如果 c[i - 1, j] ≥ c[i, j-1] b[i, j] = 2 否则 b[i, j] = 333CDc[i,j-1]c[i-1,j]30
  • 31. LCS-LENGTH(X, Y, m, n) 1 for i ← 1 to m do c[i, 0] ← 0 2 for j ← 0 to n do c[0, j] ← 0 3 for i ← 1 to m do 4 for j ← 1 to n do 5 if xi = yj 6 then c[i, j] ← c[i - 1, j - 1] + 1 7 b[i, j ] ← “↖” 8 else if c[i - 1, j] ≥ c[i, j - 1] 9 then c[i, j] ← c[i - 1, j] 10 b[i, j] ← “↑” 11 else c[i, j] ← c[i, j - 1] 12 b[i, j] ← “←” 13 return c and b运行时间: (nm)31
  • 32. 例子X = (B, D, C, A, B, A) Y = (A, B, C, B, D, A,B)0126345yjBDACAB51203467DABxiCBAB00000000000000 0 0 0 11 1 111 1 22 1 1 22 2 2 1 1 2 2 33 1 2 2 2 3 3 1 2 3 2 3 4 1 2 2 3 4 4如果 xi = yj b[i, j] = “ ” 如果 c[i - 1, j]≥c[i, j-1] b[i, j] = “  ” 否则 b[i, j] = “  ”32
  • 33. 找出最长共同子序列PRINT-LCS(b, X, i, j) 1 if i = 0 or j = 0 2 then return 3 if b[i, j] = " ↖ " 4 then PRINT-LCS(b, X, i - 1, j - 1) 5 print xi 6 elseif b[i, j] = "↑" 7 then PRINT-LCS(b, X, i - 1, j) 8 else PRINT-LCS(b, X, i, j - 1) 33
  • 34. 例题8:0-1背包问题小偷有一个可承受W的背包 有n件物品: 第i个物品价值vi 且重wi 目标: 找到xi使得对于所有的xi = {0, 1}, i = 1, 2, .., n  wixi  W 并且 xivi 最大部分背包问题34
  • 35. 最优子结构考虑最多重W的物品且价值最高 如果我们把j物品从背包中拿出来 剩下的装载一定是取自n-1个物品使得不超过载重量W – wj并且所装物品价值最高的装载35
  • 36. 0-1背包问题的动态规划 对于每一个物品i,都有两种情况需要考虑 第1种情况:物品i的重量wi<=w,小偷对物品i可拿或者不拿 P[i,w] = max{P[i-1, w], P[i-1,w-wi] + vi} 第2种情况:物品i的重量wi>w,即小偷不拿物品i P(i, w) = P(i - 1, w)步骤1P(i, w) –考虑前i件物品所能获得的最高价值,其中w是背包的承受力步骤2阶段分析:P(i,w)=P(i-1,w) 当wi< w (不够装不装)maxP(i-1,w) 够装但不装p(i-1,w-wi)+pi 够装而且装36
  • 37. Knapsack (S,W) 1 for w ← 0 to w1 - 1 do P[1, w] ← 0; 2 for w ← w1 to W do P[1, w] ← v1; 3 for i ← 2 to n do 4 for w ← 0 to W do 5 if wi > w then 6 P[i,w] ← P[i-1, w]; 7 else 8 P[i,w] ← max{P[i-1, w], P[i-1,w-wi] + vi}运行时间: (nW)37
  • 38. 0-1背包问题的动态规划000000000000000000:n1w - wiWi-10first P(i, w) = max {vi + P(i - 1, w-wi), P(i - 1, w) } 带走物品i不带走物品iiwsecond38
  • 39. P(i, w) = max {vi + P(i - 1, w-wi), P(i - 1, w) } 0000000000物品重量价值12122110332042150123451234W = 5012121212101222222210122230321015253037P(1, 1) = P(1, 2) = P(1, 3) = P(1, 4) = P(1, 5) = P(2, 1)= P(2, 2)= P(2, 3)= P(2, 4)= P(2, 5)= P(3, 1)= P(3, 2)= P(3, 3)= P(3, 4)= P(4, 5)= P(4, 1)= P(4, 2)= P(4, 3)= P(4, 4)= P(4, 5)= max{12+0, 0} = 12max{12+0, 0} = 12max{12+0, 0} = 12max{12+0, 0} = 12max{10+0, 0} = 10max{10+0, 12} = 12max{10+12, 12} = 22max{10+12, 12} = 22max{10+12, 12} = 22P(2,1) = 10P(2,2) = 12max{20+0, 22}=22max{20+10,22}=30max{20+12,22}=32P(3,1) = 10max{15+0, 12} = 15max{15+10, 22}=25max{15+12, 30}=30max{15+22, 32}=370P(0, 1) = 0wi39
  • 40. 构造最优解法000000000001234512340121212121012222222101222303210152530370从 P(n, W)开始 当往左上走物品i被带走 当直往上走物品i未被带走物品4物品2物品140
  • 41. 子问题的重复000000000000000000:n1Wi-10 P(i, w) = max {vi + P(i - 1, w-wi), P(i - 1, w) } iw例如: 所有用灰色表示的子问题都取决于P(i-1, w)41
  • 42. 子问题的重复100101108108681006282861001623823816510000000000000111111111例子: n=5, p=[6,3,5,4,6], w=[2,2,6,5,4], W=10
  • 43. 拓展1:装箱问题 (vijos 1133)有一个箱子容量为v(正整数,o≤v≤20000),同时有n个物品(o≤n≤30),每个物品有一个体积 (正整数)。要求从 n 个物品中,任取若千个装入箱内,使箱子的剩余空间为最小。 输入格式 Input Format 第一行,一个整数,表示箱子容量; 第二行,一个整数,表示有n个物品; 接下来n行,分别表示这n个物品的各自体积。 输出格式 Output Format 一个整数,表示箱子剩余空间。 样例输入 Sample Input 24 6 8 3 12 7 9 7样例输出 Sample Output 043
  • 44. 拓展2:采药 (vijos1104) 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”   如果你是辰辰,你能完成这个任务吗? 输入格式 Input Format 输入的第一行有两个整数T(1 <= T <= 1000)和M(1 <= M <= 100),用一个空格隔开,T代表总共能够用来采药的时间,M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药的价值。 输出格式 Output Format 输出包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。 样例输入 Sample Input 70 3 71 100 69 1 1 2样例输出 Sample Output 344
  • 45. 拓展3:开心的金明 (vijos 1317) 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N 元钱就行”。今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的N 元。于是,他把每件物品规定了一个重要度,分为5 等:用整数1~5 表示,第5 等最重要。他还从因特网上查到了每件物品的价格(都是整数元)。他希望在不超过N 元(可以等于N 元)的前提下,使每件物品的价格与重要度的乘积的总和最大。设第j 件物品的价格为v[j],重要度为w[j],共选中了k 件物品,编号依次为j1...jk,则所求的总和为:v[j1]*w[j1]+..+v[jk]*w[jk]请你帮助金明设计一个满足要求的购物单. 输入格式 Input Format 输入的第1 行,为两个正整数,用一个空格隔开: N m (其中N(<30000)表示总钱数,m(<25)为希望购买物品的个数。) 从第2 行到第m+1 行,第j 行给出了编号为j-1 的物品的基本数据,每行有2 个非负整数 v p (其中v 表示该物品的价格(v≤10000),p 表示该物品的重要度(1~5)) 45
  • 46. 输出格式 Output Format 输出只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的 最大值(<100000000) 样例输入 Sample Input 1000 5 800 2 400 5 300 5 400 3 200 2样例输出 Sample Output 390046
  • 47. 拓展4:金明的预算方案 (vijos 1313 )金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子: 主件 附件 电脑 打印机,扫描仪 书柜 图书 书桌 台灯,文具 工作椅 无   如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的N元。于是,他把每件物品规定了一个重要度,分为5等:用整数1~5表示,第5等最重要。他还从因特网上查到了每件物品的价格(都是10元的整数倍)。他希望在不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大。   设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品,编号依次为j1,j2,……,jk,则所求的总和为:v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。(其中*为乘号)请你帮助金明设计一个满足要求的购物单。 47
  • 48. 输入格式 Input Format 输入文件的第1行,为两个正整数,用一个空格隔开: N  m 其中N(<32000)表示总钱数,m(<60)为希望购买物品的个数。) 从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有3个非负整数 v  p  q (其中v表示该物品的价格(v<10000),p表示该物品的重要度(1~5),q表示该物品是主件还是附件。如果q=0,表示该物品为主件,如果q>0,表示该物品为附件,q是所属主件的编号) 输出格式 Output Format 输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值 (<200000)。 样例输入 Sample Input 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0样例输出 Sample Output 220048
  • 49. 例题9:石子归并描述:在一个圆形操场的四周摆放着N堆石子(N<= 100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(<=20). (!)选择一种合并石子的方案,使用权得做N-1次合并,得分的总和最小; (2)选择一种合并石子的方案,使用权得做N-1次合并,得分的总和最小; 输入数据: 第一行为石子堆数N; 第二行为每堆的石子数,每两个数之间用一个空格分隔. 输出数据: 从第一至第N行为得分最小的合并方案.第N+1行是空行.从第N+2行到第2N+1行是得分最大合并方案.每种合并方案用N行表示,其中第i行(1<=i<=N)表示第i次合并前各堆的石子数(依顺时针次序输出,哪一堆先输出均可).要求将待合并的两堆石子数以相应的负数表示. 输入输出范例: 输入: 4 4 5  9  4   输出: 最小=43 最大=5449
  • 50. 输入: 4 4 5  9  4   输出: -4  5  9 -4 -8 -5 9 -13  -9 22 4  -5  -9  4 4  -14  -4 -4  -18 22拓:输出合并的方案:50
  • 51. 用〔i,j〕表示一个从第i堆数起,顺时针数j堆时的子序列 {第i堆、第i+1堆、……、第(i+j-1)mod n堆} 步骤1f〔i,j〕──将子序列〔i,j〕中的j堆石子合并成一堆的最佳得分和;(结果数组) c〔i,j〕──将〔i,j〕一分为二,其中子序列1的堆数;(记录分隔点)打印合并方案时使用51
  • 52. 显然,对每一堆石子来说,它的 f〔i,1〕=0 c〔i,1〕=0 (1≤i≤N) 对于子序列〔i,j〕来说,若求最小得分总和,f〔i,j〕的初始值为∞; 若求最大得 分总和,f〔i,j〕的初始值为0。(1≤i≤N,2≤j≤N)。 规划的方向是顺推。先考虑含二堆石子的N个子序列(各子序列分别从第1堆、第2堆、 ……、第N堆数起,顺时针数2堆)的合并方案 f〔1,2〕,f〔2,2〕,……,f〔N,2〕 c〔1,2〕,c〔2,2〕,……,c〔N,2〕 然后考虑含三堆石子的N个子序列(各子序列分别从第1堆、第2堆、……、第N堆 数起,顺时针数3堆)的合并方案 f〔1,3〕,f〔2,3〕,……,f〔N,3〕 c〔1,3〕,c〔2,3〕,……,c〔N,3〕 …… 依次类推,直至考虑了含N堆石子的N个子序列(各子序列分别从第1堆、第2堆、 … …、第N堆数起,顺时针数N堆)的合并方案 f〔1,N〕,f〔2,N〕,……,f〔N,N〕 c〔1,N〕,c〔2,N〕,……,c〔N,N〕 最后,在子序列〔1,N〕,〔2,N〕,……,〔N,N〕中,选择得分总和(f值)最 小(或最大)的一个子序列〔i,N〕(1≤i≤N),由此出发倒推合并过程。 阶段分析:52
  • 53. 例如对(图6.2-4)中的6堆石子,按动态规划方程顺推最小得分和。 依次得出含 二堆石子的6个子序列的合并方案 f〔1,2〕=7 f〔2,2〕=10 f〔3 ,2〕=11 c〔1,2〕=1 c〔2,2〕=1 c〔3,2〕=1 f〔4,2〕=9 f〔5,2〕=6 f〔6,2〕=5 c〔4,2〕=1 c〔5, 2〕=1 c〔6,2〕=1 含三堆石子的6个子序列的合并方案 f〔1,3〕=20 f〔2,3〕=25 f〔3,3〕=24 c〔1,3〕=2 c〔2,3〕=2 c〔3,3〕=1 f〔4,3〕=17 f〔5,3〕=14 f〔6,3〕=14 c〔4,3〕=1 c〔5,3〕=1 c〔6,3〕=2 含四堆石子的6个子序列的合并方案 f〔1,4〕=36 f〔2,4〕=38 f〔3,4〕=34 c〔1,4〕=2 c〔2,4〕=2 c〔3,4〕=1 f〔4,4〕=28 f〔5,4〕=26 f〔6,4〕=29 c〔4,4〕=1 c〔5,4〕=2 c〔6,4〕=3 例题:3 4 6 5 4 2 53
  • 54. 步骤2:状态转移方程F(I,j)= f (i,1)=0 j=1, 1<=i<=nmax{f〔i,k〕+f〔x,j-k〕+t} , 1<=k<=j-1其中,x=(i+k-1) mod n +1 即第i堆起,顺时针数k+1堆的堆序号。 t=a[i]+a[i+1]+…..+a[j], 即将分开的两堆合并为一堆的得分。c〔i,j〕=k│ f〔i,j〕=f〔i,k〕+f〔x,j-k〕+t       (2≤j≤n,1≤i≤n) 54
  • 55. 附加信息:打印合并方案55
  • 56. 拓展1:能量项链 (vijos 1312) 在Mars星球上,每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸盘是Mars人吸收能量的一种器官)的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m,尾标记为r,后一颗能量珠的头标记为r,尾标记为n,则聚合后释放的能量为(Mars单位),新产生的珠子的头标记为m,尾标记为n。 需要时,Mars人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。 例如:设N=4,4颗珠子的头标记与尾标记依次为(2,3) (3,5) (5,10) (10,2)。我们用记号⊕表示两颗珠子的聚合操作,(j⊕k)表示第j,k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为: (4⊕1)=10*2*3=60。 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3)=10*2*3+10*3*5+10*5*10=710。 56
  • 57. 输入格式 Input Format 输入文件的第一行是一个正整数N(4≤N≤100),表示项链上珠子的个数。第二行是N个用空格隔开的正整数,所有的数均不超过1000。第i个数为第i颗珠子的头标记(1≤i≤N),当1≤i<N时,第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。 至于珠子的顺序,你可以这样确定:将项链放到桌面上,不要出现交叉,随意指定第一颗珠子,然后按顺时针方向确定其他珠子的顺序。 输出格式 Output Format 输出文件只有一行,是一个正整数E(E≤2.1*109),为一个最优聚合顺序所释放的总能量。   样例输入 Sample Input 4 2 3 5 10样例输出 Sample Output 71057
  • 58. 拓展2:数字游戏 (vijos 1218)【问题描述】丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共n个),你要按顺序将其分为m个部分,各部分内的数字相加,相加所得的m个结果对10取模后再相乘,最终得到一个数k。游戏的要求是使你所得的k最大或者最小。 例如,对于下面这圈数字(n=4,m=2): 当要求最小值时,((2-1) mod 10)×((4+3) mod 10)=1×7=7,要求最大值时,为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是,无论是负数还是正数,对10取模的结果均为非负值。 丁丁请你编写程序帮他赢得这个游戏。24-1358
  • 59. 【输入格式】输入文件第一行有两个整数,n(1≤n≤50)和m(1≤m≤9)。以下n行每行有个整数,其绝对值不大于104,按顺序给出圈中的数字,首尾相接。 【输出格式】输出文件有两行,各包含一个非负整数。第一行是你程序得到的最小值,第二行是最大值。 【输入样例】 4 2 4 3 -1 2【输出样例】 7 8159
  • 60. 编程练习60