信息学竞赛3-9动态规划

《信息学竞赛3-9动态规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划最长非降子序列47,36,52,46,45,28,46,69,14,42对给定的正整数序列，从序列中删除若干个数字，使剩下的组成非降子序列。求最长的非降子序列最长非降子序列设数组a[n]和b[n]，a[n]表示数字序列b[i]表示第i个数字到最后一位数字的最长非降子序列长度。明显：b[n-1]=1a[n]47365246452846691442b[n]1最长非降子序列a[n]47365246452846691442b[n]1a[n]47365246452846691442b[n]21a[n]4736

2、5246452846691442b[n]121最长非降子序列a[n]47365246452846691442b[n]2121a[n]47365246452846691442b[n]32121a[n]47365246452846691442b[n]332121最长非降子序列a[n]47365246452846691442b[n]3332121a[n]47365246452846691442b[n]23332121a[n]47365246452846691442b[n]423332121最长非降子序列a[n]4

3、7365246452846691442b[n]3423332121找到b[n]最大值从左到右，找到max(b[n]),max(b[n])-1,max(b[n])-2，…，1a[n]47365246452846691442b[n]3423332121最长非降子序列最长序列=436464669a[n]47365246452846691442b[n]3423332121最长非降子序列递推关系对于0≤i

4、[j],b[j+1],…,b[n-1])+1边界条件：b[n-1]=1；a[n]47365246452846691442b[n]3423332121数字三角形的最优路径如下示出了一个数字三角形请编一个程序计算从顶至底的一条路径，使该路径所经过的数字的总和最大。●每一步可沿下方或右斜线向下走；●1＜三角形行数≤100；●三角形中的数字为整数0，1，…99；738274481045265数字三角形的最优路径738274481045265a11a21a22a41a42a43a44a31a32a33a51a52a5

5、3a54a55数字三角形的最优路径——最大值设结构和a数组相同的b数组bij表示点i，j到底的最大路径738274481045265712101045265bij=aij+max(bi+1j,bi+1j+1)数字三角形的最优路径——最大值设结构和a数组相同的b数组bij表示点i，j到底的最大路径738274481045265302321712101020131045265bij=aij+max(bi+1j,bi+1j+1)数字三角形Input输入第1行是目标数字，第2行是三角形的行数N。以后的N行分别是从最

6、顶层到最底层的每一层中的数字。Output输出仅有一行包含一个整数（表示要求的最大总和）。数字三角形SampleInput5738810274445265SampleOutput30数字三角形的最优路径——最小值设结构和a数组相同的b数组bij表示点i，j到底的最小路径7382744810452651710146969147645265bij=aij+min(bi+1j,bi+1j+1)边值矩形的最优路径1012391342272519343924352041253226423627301639322316

7、3121402220412532312245246718边值矩形的最优路径一个n行n列的边值矩形，每个点可向右或向下两个方向选择求左上角到右下角的路径中，所经过数值和最大的路径边值矩形的最优路径r54表示横线边值c45表示竖线边值aij表示点ij到右下角的路径最大值边值矩形的最优路径r11r12r13r14r21r22r23r24r31r32r33r34r41r42r43r44r51r52r53r54c11c12c13c14c15c21c22c23c24c25c31c32c33c34c35c41c42c43

8、c44c45边值矩形的最优路径r11r12r13r14r21r22r23r24r31r32r33r34r41r42r43r44r51r52r53r54c11c12c13c14c15c21c22c23c24c25c31c32c33c34c35c41c42c43c44c45a11a12a13a14a15a21a22a23a24a25a31a32a33a34a35a41a42a43a44a45a51a52a53a54a