信息学竞赛3-9动态规划.ppt
动态规划,最长非降子序列,47,36,52,46,45,28,46,69,14,42对给定的正整数序列，从序列中删除若干个数字，使剩下的组成非降子序列。求最长的非降子序列,最长非降子序列,设数组an和bn，an表示数字序列bi表示第i个数字到最后一位数字的最长非降子序列长度。明显：bn-1=1,最长非降子序列,最长非降子序列,最长非降子序列,最长非降子序列,找到bn最大值从左到右，找到max(bn),max(bn)-1,max(bn)-2，1,最长非降子序列,最长序列=4 36 46 46 69,最长非降子序列,递推关系对于0ijn，找到ajai且bj=max(bj,bj+1,bn-1)bi=max(bj,bj+1,bn-1)+1边界条件：bn-1=1；,数字三角形的最优路径,如下示出了一个数字三角形,请编一个程序计算从顶至底的一条路径，使该路径所经过的数字的总和最大。每一步可沿下方或右斜线向下走；1三角形行数100；三角形中的数字为整数0，1，99；,数字三角形的最优路径,数字三角形的最优路径最大值,设结构和a数组相同的b数组bij表示点i，j到底的最大路径,bij=aij+max(bi+1j,bi+1j+1),数字三角形的最优路径最大值,设结构和a数组相同的b数组bij表示点i，j到底的最大路径,bij=aij+max(bi+1j,bi+1j+1),数字三角形,Input输入第1行是目标数字，第2行是三角形的行数N。以后的N行分别是从最顶层到最底层的每一层中的数字。Output输出仅有一行包含一个整数（表示要求的最大总和）。,数字三角形,Sample Input573 88 1 02 7 4 44 5 2 6 5Sample Output30,数字三角形的最优路径最小值,设结构和a数组相同的b数组bij表示点i，j到底的最小路径,bij=aij+min(bi+1j,bi+1j+1),边值矩形的最优路径,边值矩形的最优路径,一个n行n列的边值矩形，每个点可向右或向下两个方向选择求左上角到右下角的路径中，所经过数值和最大的路径,边值矩形的最优路径,r54表示横线边值c45表示竖线边值aij表示点ij到右下角的路径最大值,边值矩形的最优路径,边值矩形的最优路径,a11 a12 a13 a14 a15a21 a22 a23 a24 a25a31 a32 a33 a34 a35a41 a42 a43 a44 a45a51 a52 a53 a54 a55,边值矩形的最优路径,a34的值等于a44+c34和a35+r34的较大值a34=Max(a44+c34,a35+r34),边值矩形的最优路径,a44的值等于a54+c44和a45+r44的较大值a44=Max(a54+c44,a45+r44),边值矩形的最优路径,边界条件：a55=0a54=a55+r54a45=a55+c45,buy low,buy lower,“逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀:逢低吸纳,越低越买 这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。给定连续的N天中每天的股价。你可以在任何一天购买一次股票，但是购买时的股价一定要比你上次购买时的股价低。写一个程序，求出最多能买几次股票。,buy low,buy lower,以下面这个表为例,某几天的股价是:这个例子中,聪明的投资者(按上面的定义)，如果每次买股票时的股价都比上一次买时低，那么他最多能买4次股票。一种买法如下(可能有其他的买法):天数 25610 股价 69 68 64 62,buy low,buy lower,Input第1行:N(1=N=5000),表示能买股票的天数。第2行以下:N个正整数(可能分多行)，第i个正整数表示第i天的股价.这些正整数大小不会超过longintOutput输出只有一行，输出两个整数：*能够买进股票的天数*长度达到这个值的股票购买方案数量 在计算解的数量的时候，如果两个解所组成的字符串相同，那么这样的两个解被认为是相同的（只能算做一个解）。因此，两个不同的购买方案可能产生同一个字符串，这样只能计算一次。,buy low,buy lower,Sample Input1268 69 54 64 68 64 70 67 78 62 98 87Sample Output4 2,回文词,回文词是一种对称的字符串也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的任务是写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文词（“dAb3bAd”或“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。,回文词,Input第一行包含一个整数N，表示给定字符串的长度，3=N=5000 第二行是一个长度为N的字符串，字符串由大小写字母和数字构成。Output一个整数，表示需要插入的最少字符数。,回文词,Sample Input5Ab3bdSample Output2,邮局,一些村庄建在一条笔直的高速公路边上，我们用一条坐标轴来描述这条公路，每个村庄的坐标都是整数，没有两个村庄的坐标相同。两个村庄的距离定义为坐标之差的绝对值。我们需要在某些村庄建立邮局。使每个村庄使用与它距离最近的邮局，建立邮局的原则是：所有村庄到各自使用的邮局的距离总和最小。数据规模：1=村庄数=300,1=邮局数=30,1=村庄坐标=10000）,邮局,Input2行 第一行:n m 表示有n个村庄，建立m个邮局 第二行:a1 a2 a3.an 表示n个村庄的坐标 Output1行 第一行:l l表示最小距离总和,邮局,Sample Input10 51 2 3 6 7 9 11 22 44 50Sample Output9,0/1背包问题,给定n种物品和一背包.物品i的重量是wi,其价格是pi,背包的容量为weight.问:应该如何选择装入背包的物品,使得装入背包中的总价值最大?在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包或不装入背包.不能将物品i装入背包多次,也不能只装入部分的物品,0/1背包问题,Input输入共四行。第一行为背包容量weight；第二行为物品件数n；(n=1000)第三行为n件物品的重量wi；(wi=1000)第四行为各个物品对应的价值pi。(pi=1000)Output输出装入背包物品的总价值。,0/1背包问题,Sample Input1142 4 6 76 10 12 13Sample Output23,单击此处添加标题,单击此处添加标题,单击此处添加段落文字内容,单击此处添加段落文字内容,单击此处添加段落文字内容,单击此处添加段落文字内容,单击此处添加标题,双击添加标题文字,单击此处添加段落文字内容单击此处添加段落文字内容单击此处添加段落文字内容,双击添加标题文字,单击此处添加段落文字内容单击此处添加段落文字内容单击此处添加段落文字内容,双击添加标题文字,单击此处添加段落文字内容单击此处添加段落文字内容单击此处添加段落文字内容,单击此处添加标题,双击添加标题文字,单击此处添加段落文字内容单击此处添加段落文字内容,单击此处添加段落文字内容单击此处添加段落文字内容,单击此处添加段落文字内容单击此处添加段落文字内容,单击此处添加段落文字内容单击此处添加段落文字内容,单击此处添加标题,此处添加内容,此处添加内容,此处添加内容,双击添加标题文字,单击此处添加段落文字内容单击此处添加段落文字内容,单击此处添加段落文字内容单击此处添加段落文字内容,单击此处添加段落文字内容单击此处添加段落文字内容,单击此处添加段落文字内容,单击此处添加段落文字内容,双击添加标题文字,单击此处添加段落文字内容 单击此处添加段落文字内容,单击此处添加段落文字内容 单击此处添加段落文字内容,单击此处添加标题,单击此处添加标题,单击此处添加段落文字内容,此处添加内容,此处添加内容,单击此处添加段落文字内容,此处添加内容,单击此处添加段落文字内容,此处添加内容,单击此处添加段落文字内容,此处添加内容,单击此处添加段落文字内容,此处添加内容,单击此处添加段落文字内容,单击此处添加标题,单击添加,单击添加内容文字,单击添加,单击添加内容文字,单击添加,单击添加内容文字,单击添加,单击添加内容文字,单击此处添加标题,单击此处添加段落文字内容,单击此处添加段落文字内容单击此处添加段落文字内容单击此处添加段落文字内容,单击此处添加段落文字内容单击此处添加段落文字内容单击此处添加段落文字内容,单击此处添加段落文字内容,单击此处添加段落文字内容单击此处添加段落文字内容单击此处添加段落文字内容,单击此处添加段落文字内容单击此处添加段落文字内容单击此处添加段落文字内容,本次课程结束，谢谢欣赏,
