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

动态规划 最长非降子序列 47 36 52 46 45 28 46 69 14 42对给定的正整数序列 从序列中删除若干个数字 使剩下的组成非降子序列 求最长的非降子序列 最长非降子序列 设数组a n 和b n a n 表示数字序列b i 表示第i个数字到最后一位数字的最长非降子序列长度 明显 b n 1 1 最长非降子序列 最长非降子序列 最长非降子序列 最长非降子序列 找到b n 最大值从左到右 找到max b n max b n 1 max b n 2 1 最长非降子序列 最长序列 436464669 最长非降子序列 递推关系对于0 i j n 找到a j a i 且b j max b j b j 1 b n 1 b i max b j b j 1 b n 1 1边界条件 b n 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输出仅有一行包含一个整数 表示要求的最大总和 数字三角形 SampleInput5738810274445265SampleOutput30 数字三角形的最优路径 最小值 设结构和a数组相同的b数组bij表示点i j到底的最小路径 bij aij min bi 1j bi 1j 1 边值矩形的最优路径 边值矩形的最优路径 一个n行n列的边值矩形 每个点可向右或向下两个方向选择求左上角到右下角的路径中 所经过数值和最大的路径 边值矩形的最优路径 r54表示横线边值c45表示竖线边值aij表示点ij到右下角的路径最大值 边值矩形的最优路径 边值矩形的最优路径 a11a12a13a14a15a21a22a23a24a25a31a32a33a34a35a41a42a43a44a45a51a52a53a54a55 边值矩形的最优路径 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 buylow buylower 逢低吸纳 是炒股的一条成功秘诀 如果你想成为一个成功的投资者 就要遵守这条秘诀 逢低吸纳 越低越买 这句话的意思是 每次你购买股票时的股价一定要比你上次购买时的股价低 按照这个规则购买股票的次数越多越好 看看你最多能按这个规则买几次 给定连续的N天中每天的股价 你可以在任何一天购买一次股票 但是购买时的股价一定要比你上次购买时的股价低 写一个程序 求出最多能买几次股票 buylow buylower 以下面这个表为例 某几天的股价是 这个例子中 聪明的投资者 按上面的定义 如果每次买股票时的股价都比上一次买时低 那么他最多能买4次股票 一种买法如下 可能有其他的买法 天数25610股价69686462 buylow buylower Input第1行 N 1 N 5000 表示能买股票的天数 第2行以下 N个正整数 可能分多行 第i个正整数表示第i天的股价 这些正整数大小不会超过longintOutput输出只有一行 输出两个整数 能够买进股票的天数 长度达到这个值的股票购买方案数量在计算解的数量的时候 如果两个解所组成的字符串相同 那么这样的两个解被认为是相同的 只能算做一个解 因此 两个不同的购买方案可能产生同一个字符串 这样只能计算一次 buylow buylower SampleInput12686954646864706778629887SampleOutput42 回文词 回文词是一种对称的字符串 也就是说 一个回文词 从左到右读和从右到左读得到的结果是一样的 任意给定一个字符串 通过插入若干字符 都可以变成一个回文词 你的任务是写一个程序 求出将给定字符串变成回文词所需插入的最少字符数 比如字符串 Ab3bd 在插入两个字符后可以变成一个回文词 dAb3bAd 或 Adb3bdA 然而 插入两个以下的字符无法使它变成一个回文词 回文词 Input第一行包含一个整数N 表示给定字符串的长度 3 N 5000第二行是一个长度为N的字符串 字符串由大小写字母和数字构成 Output一个整数 表示需要插入的最少字符数 回文词 SampleInput5Ab3bdSampleOutput2 邮局 一些村庄建在一条笔直的高速公路边上 我们用一条坐标轴来描述这条公路 每个村庄的坐标都是整数 没有两个村庄的坐标相同 两个村庄的距离定义为坐标之差的绝对值 我们需要在某些村庄建立邮局 使每个村庄使用与它距离最近的邮局 建立邮局的原则是 所有村庄到各自使用的邮局的距离总和最小 数据规模 1 村庄数 300 1 邮局数 30 1 村庄坐标 10000 邮局 Input2行第一行 nm 表示有n个村庄 建立m个邮局 第二行 a1a2a3 an 表示n个村庄的坐标 Output1行第一行 l l表示最小距离总和 邮局 SampleInput10512367911224450SampleOutput9 0 1背包问题 给定n种物品和一背包 物品i的重量是w i 其价格是p i 背包的容量为weight 问 应该如何选择装入背包的物品 使得装入背包中的总价值最大 在选择装入背包的物品时 对每种物品i只有两种选择 即装入背包或不装入背包 不能将物品i装入背包多次 也不能只装入部分的物品 0 1背包问题 Input输入共四行 第一行为背包容量weight 第二行为物品件数n n 1000 第三行为n件物品的重量w i w i 1000 第四行为各个物品对应的价值p i p i 1000 Output输出装入背包物品的总价值 0 1背包问题 SampleInput11424676101213SampleOutput23 单击此处添加标题 单击此处添加标题 单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加标题 双击添加标题文字 单击此处添加段落文字内容单击此处添加段落文字内容单击此处添加段落文字内容 双击添加标题文字 单击此处添加段落文字内容单击此处添加段落文字内容单击此处添加段落文字内容 双击添加标题文字 单击此处添加段落文字内容单击此处添加段落文字内容单击此处添加段落文字内容 单击此处添加标题 双击添加标题文字 单击此处添加段落文字内容单击此处添加段落文字内容 单击此处添加段落文字内容单击此处添加段落文字内容 单击此处添加段落文字内容单击此处添加段落文字内容 单击此处添加段落文字内容单击此处添加段落文字内容 单击此处添加标题 此处添加内容 此处添加内容 此处添加内容 双击添加标题文字 单击此处添加段落文字内容单击此处添加段落文字内容 单击此处添加段落文字内容单击此处添加段落文字内容 单击此处添加段落文字内容单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加段落文字内容 双击添加标题文字 单击此处添加段落文字内容单击此处添加段落文字内容 单击此处添加段落文字内容单击此处添加段落文字内容 单击此处添加标题 单击此处添加标题 单击此处添加段落文字内容 此处添加内容 此处添加内容 单击此处添加段落文字内容 此处添加内容 单击此处添加段落文字内容 此处添加内容 单击此处添加段落文字内容 此处添加内容 单击此处添加段落文字内容 此处添加内容 单击此处添加段落文字内容 单击此处添加标题 单击添加 单击添加内容文字 单击添加 单击添加内容文字 单击添加 单击添加内容文字 单击添加 单击添加内容文字 单击此处添加标题 单击