《信息学竞赛3-9动态规划》由会员分享，可在线阅读，更多相关《信息学竞赛3-9动态规划（52页珍藏版）》请在金锄头文库上搜索。
1、动态规划最长非降子序列47,36,52,46,45,28,46,69,14,42对给定的正整数序列，从序列中删除若干 个数字，使剩下的组成非降子序列。求最长 的非降子序列最长非降子序列设数组an和bn， an表示数字序列 bi表示第i个数字到最后一位数字的最 长非降子序列长度。 明显：bn-1=1an47365246452846691442bn1最长非降子序列an47365246452846691442bn1an47365246452846691442bn21an47365246452846691442bn121最长非降子序列an47365246452846691442bn2121an4736
2、5246452846691442bn32121an47365246452846691442bn332121最长非降子序列an47365246452846691442bn3332121an47365246452846691442bn23332121an47365246452846691442bn423332121最长非降子序列an47365246452846691442bn3423332121找到bn最大值 从左到右，找到max(bn), max(bn)- 1, max(bn)-2，1an47365246452846691442bn3423332121最长非降子序列最长序列= 4 36 46 4
3、6 69an47365246452846691442bn3423332121最长非降子序列递推关系 对于0ijn， 找到ajai 且bj=max(bj,bj+1, bn-1) bi=max(bj, bj+1, bn-1)+1 边界条件：bn-1=1；an47365246452846691442bn3423332121数字三角形的最优路径如下示出了一个数字三 角形请编一个程序计算从顶 至底的一条路径，使该路径 所经过的数字的总和最大。 每一步可沿下方或 右斜线向下走； 1三角形行数 100； 三角形中的数字为 整数0，1，99； 7 38274481045265数字三角形的最优路径7 38274
4、481045265a11 a21a22a41a42a43a44a31a32a33a51a52a53a54a55数字三角形的最优路径最大值设结构和a数组相同的b数组 bij表示点i，j到底的最大路径7 382744810452657 12 10 10 45265bij = aij+max (bi+1j, bi+1j+1) 数字三角形的最优路径最大值设结构和a数组相同的b数组 bij表示点i，j到底的最大路径7 3827448104526530 23 217 12 10 1020 13 1045265 bij = aij+max (bi+1j, bi+1j+1) 数字三角形Input 输入第1行是
5、目标数字，第2行是三角形的行数 N。以后的N行分别是从最顶层到最底层的每一层 中的数字。 Output输出仅有一行包含一个整数（表示要求的最大 总和）。数字三角形Sample Input 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5Sample Output 30数字三角形的最优路径最小值设结构和a数组相同的b数组 bij表示点i，j到底的最小路径7 3827448104526517 10 14696914 7645265 bij = aij+min(bi+1j, bi+1j+1) 边值矩形的最优路径10 12 39 1342 27 25 1934 39 24 3520 41
6、 25 3226 42 36 2730 16 39 32 2316 31 21 40 2220 41 25 32 3122 45 24 67 18边值矩形的最优路径一个n行n列的边值 矩形，每个点可向右或 向下两个方向选择 求左上角到右下角 的路径中，所经过数值 和最大的路径边值矩形的最优路径r54表示横线边值 c45表示竖线边值 aij表示点ij到右下角 的路径最大值边值矩形的最优路径r11 r12 r13 r14r21 r22 r23 r24r31 r32 r33 r34r41 r42 r43 r44r51 r52 r53 r54c11 c12 c13 c14 c15c21 c22 c23
7、 c24 c25c31 c32 c33 c34 c35c41 c42 c43 c44 c45边值矩形的最优路径r11 r12 r13 r14r21 r22 r23 r24r31 r32 r33 r34r41 r42 r43 r44r51 r52 r53 r54c11 c12 c13 c14 c15c21 c22 c23 c24 c25c31 c32 c33 c34 c35c41 c42 c43 c44 c45a11 a12 a13 a14 a15a21 a22 a23 a24 a25a31 a32 a33 a34 a35a41 a42 a43 a44 a45a51 a52 a53 a54 a5
8、5边值矩形的最优路径a34的值等于a44+c34和a35+r34的较大 值 a34 =Max(a44+c34,a35+r34)边值矩形的最优路径a44的值等于a54+c44和a45+r44的较大 值 a44 =Max(a54+c44,a45+r44)边值矩形的最优路径边界条件：a55=0 a54=a55+r54 a45=a55+c45buy low,buy lower“逢低吸纳”是炒股的一条成功秘诀。如果你想成 为一个成功的投资者，就要遵守这条秘诀: 逢低吸纳,越低越买 这句话的意思是：每次你购买 股票时的股价一定要比你上次购买时的股价低.按照这个 规则购买股票的次数越多越好，看看你最多能按这
9、个规 则买几次。 给定连续的N天中每天的股价。你可以在任何一天 购买一次股票，但是购买时的股价一定要比你上次购买 时的股价低。写一个程序，求出最多能买几次股票。buy low,buy lower以下面这个表为例, 某几天的股价是: 这个例子中, 聪明的投资者(按上面的定义)，如 果每次买股票时的股价都比上一次买时低，那么他 最多能买4次股票。一种买法如下(可能有其他的买 法): 天数 2 5 6 10 股价 69 68 64 62 天数123456789101112 股价686954646864706778629887buy low,buy lowerInput 第1行: N (1 = N =
10、 5000), 表示能买股票的天数。 第2行以下: N个正整数 (可能分多行) ，第i个正整数表示第i天的股 价. 这些正整数大小不会超过longintOutput输出只有一行，输出两个整数： * 能够买进股票的天数 * 长度达到这个值的股票购买方案数量 在计算解的数量的时候，如果两个解所组成的字符串相同，那么 这样的两个解被认为是相同的（只能算做一个解）。因此，两个不同的 购买方案可能产生同一个字符串，这样只能计算一次。buy low,buy lowerSample Input 12 68 69 54 64 68 64 70 67 78 62 98 87Sample Output 4 2回文词 回文词是一种对称的字符串也就是
