信息学竞赛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 Input 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output 30,数字三角形的最优路径最小值,设结构和a数组相同的b数组 bij表示点i，j到底的最小路径,bij = aij+min(bi+1j, bi+1j+1),边值矩形的最优路径,边值矩形的最优路径,一个n行n列的边值矩形，每个点可向右或向下两个方向选择 求左上角到右下角的路径中，所经过数值和最大的路径,边值矩形的最优路径,r54表示横线边值 c45表示竖线边值 aij表示点ij到右下角的路径最大值,边值矩形的最优路径,边值矩形的最优路径,a11 a12 a13 a14 a15 a21 a22 a23 a24 a25 a31 a32 a33 a34 a35 a41 a42 a43 a44 a45 a51 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=0 a54=a55+r54 a45=a55+c45,buy low,buy lower,“逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀: 逢低吸纳,越低越买 这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。 给定连续的N天中每天的股价。你可以在任何一天购买一次股票，但是购买时的股价一定要比你上次购买时的股价低。写一个程序，求出最多能买几次股票。,buy low,buy lower,以下面这个表为例, 某几天的股价是: 这个例子中, 聪明的投资者(按上面的定义)，如果每次买股票时的股价都比上一次买时低，那么他最多能买4次股票。一种买法如下(可能有其他的买法): 天数 2 5 6 10 股价 69 68 64 62,buy low,buy lower,Input 第1行: N (1 = N = 5000), 表示能买股票的天数。 第2行以下: N个正整数 (可能分多行) ，第i个正整数表示第i天的股价. 这些正整数大小不会超过longint Output 输出只有一行，输出两个整数： * 能够买进股票的天数 * 长度达到这个值的股票购买方案数量 在计算解的数量的时候，如果两个解所组成的字符串相同，那么这样的两个解被认为是相同的（只能算做一个解）。因此，两个不同的购买方案可能产生同一个字符串，这样只能计算一次。,buy low,buy lower,Sample Input 12 68 69 54 64 68 64 70 67 78 62 98 87 Sample Output 4 2,回文词,回文词是一种对称的字符串也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的任务是写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。 比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文词（“dAb3bAd”或“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。,回文词,Input 第一行包含一个整数N，表示给定字符串的长度，3=N=5000 第二行是一个长度为N的字符串，字符串由大小写字母和数字构成。 Output 一个整数，表示需要插入的最少字符数。,回文词,Sample Input 5 Ab3bd Sample Output 2,邮局,一些村庄建在一条笔直的高速公路边上，我们用一条坐标轴来描述这条公路，每个村庄的坐标都是整数，没有两个村庄的坐标相同。两个村庄的距离定义为坐标之差的绝对值。我们需要在某些村庄建立邮局。使每个村庄使用与它距离最近的邮局，建立邮局的原则是：所有村庄到各自使用的邮局的距离总和最小。 数据规模：1=村庄数=300, 1=邮局数=30, 1=村庄坐标=10000）,邮局,Input 2行 第一行:n m 表示有n个村庄，建立m个邮局 第二行:a1 a2 a3 an 表示n个村庄的坐标 Output 1行 第一行:l l表示最小距离总和,邮局,Sample Input 10 5 1 2 3 6 7 9 11 22 44 50 Sample Output 9,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 Input 11 4 2 4 6 7 6 10 12 13 Sample Output 23,单击此处添加标题,单击此处添加标题,单击此处添加段落文字内容,单击此处添加段落文字内容,单击此处添加段落文字内容,单击此处添加段落文字内容,单击此处添加标题,双击添加标题文字,单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加段落文字内容,双击添加标题文字,单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加段落文字内容,双击添加标题文字,单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加段落文字内容,单击此处添加标题,双击添加标题文字,单击此处添加段落文字内容 单击此处添加段落文字内容,单击此处添加段落文字内容 单击此处添加段落文字内容,单击此处添加段落文字内容 单击此处添加段落文字内容,单击此处添加段落文字内容 单击此处添加段落文字内容,单击此处添加标题,此处添加内容,此处添加内容,此处添加内容,双击添加 标题文字,单击此处添加段落文字内容 单击此处添加段落文字内容,单击此处添加段落文字内容 单击此处添加段落文字内容,单击此处添加段落文字内容 单击此处添加段落文字内容,单击此处添加段落文字内容,单击此处添加段落文字内容,双击添加 标题文字,单击此处添加段落文字内容 单击此处添加段落文字内容,单击此处添加段落文字内容 单击此处添加段落文字内容,单击此处添加标题,单击此处添加标题,单击此处添加 段落文字内容,此处添加内容,此处添加内容,单击此处添加 段落文字内容,此处添加内容,单击此处添加 段落文字内容,此处添加内容,单击此处添加 段落文字内容,此处添加内容,单击此处添加 段落文字内容,此处添加内容,单击此处添加 段落文字内容,单击此处添加标题,单击添加,单击添加内容文字,单击添加,单击添加内容文字,单击添加,单击添加内容文字,单击添加,单击添加内容文字,单击此处添加标题