当前位置:首页 >> 学科竞赛 >> 信息学竞赛3 - 9动态规划

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


动态规划

最长非降子序列
? 47,36,52,46,45,28,46,69,14,42 ? 对给定的正整数序列,从序列中删除若干 个数字,使剩下的组成非降子序列。求最 长的非降子序列

最长非降子序列
a[n] 47 b[n] 36 52 46 45 28 46 69 14 42 1

? 设

数组a[n]和b[n], ? a[n]表示数字序列 ? b[i]表示第i个数字到最后一位数字的最长 非降子序列长度。 ? 明显:b[n-1]=1

最长非降子序列
a[n] 47 b[n] 36 52 46 45 28 46 69 14 42 1

a[n] 47 b[n]

36

52

46

45

28

46

69

14 2

42 1

a[n] 47 b[n]

36

52

46

45

28

46

69 1

14 2

42 1

最长非降子序列
a[n] 47 b[n] 36 52 46 45 28 46 2 69 1 14 2 42 1

a[n] 47 b[n]

36

52

46

45

28 3

46 2

69 1

14 2

42 1

a[n] 47 b[n]

36

52

46

45 3

28 3

46 2

69 1

14 2

42 1

最长非降子序列
a[n] 47 b[n] 36 52 46 3 45 3 28 3 46 2 69 1 14 2 42 1

a[n] 47 b[n]

36

52 2

46 3

45 3

28 3

46 2

69 1

14 2

42 1

a[n] 47 b[n]

36 4

52 2

46 3

45 3

28 3

46 2

69 1

14 2

42 1

最长非降子序列
a[n] 47 b[n] 3 36 4 52 2 46 3 45 3 28 3 46 2 69 1 14 2 42 1

? 找到b[n]最大值 ? 从左到右,找到max(b[n]), max(b[n])-1, max(b[n])-2,?,1
a[n] 47 b[n] 3 36 4 52 2 46 3 45 3 28 3 46 2 69 1 14 2 42 1

最长非降子序列
a[n] 47 b[n] 3 36 4 52 2 46 3 45 3 28 3 46 2 69 1 14 2 42 1

? 最长序列= 4 ? 36 46 46 69

最长非降子序列
a[n] 47 b[n] 3 36 4 52 2 46 3 45 3 28 3 46 2 69 1 14 2 42 1

? ? ? ? ? ?

递推关系 对于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;

7

3
8 2 4 5 7 2 1

8
0 4 6 4 5

数字三角形的最优路径

a11 a21 a22 a31 a32 a33 a41 a42 a43 a44 a51 a52 a53 a54 a55

7 3 8

8
2 4 5 7

1
4 2

0
4 6 5

数字三角形的最优路径——最大值
? 设结构和a数组相同的b数组 ? bij表示点i,j到底的最大路径

7 3
8 1

8
0

2
4 5

7
2

4
6

4
5

7 12 10 10 4 5 2 6 5

bij = aij+max (bi+1j, bi+1j+1)

数字三角形的最优路径——最大值
? 设结构和a数组相同的b数组 ? bij表示点i,j到底的最大路径

7 3 8

8
2 4 5 7

1
4 2

0
4 6 5

30 23 21 20 13 10 7 12 10 10 4 5 2 6 5

bij = aij+max (bi+1j, bi+1j+1)

数字三角形
? Input
输入第1行是目标数字,第2行是三角形的行数N 。以后的N行分别是从最顶层到最底层的每一层 中的数字。

? Output
输出仅有一行包含一个整数(表示要求的最大总 和)。

数字三角形
Sample Input
5 7 38 810 2744 45265

Sample Output 30

数字三角形的最优路径——最小值
? 设结构和a数组相同的b数组 ? bij表示点i,j到底的最小路径

7 3 8 2 7 1 4 8 0 4

4

5

2

6

5

17 10 14 14 7 6 6 9 6 9 4 5 2 6 5

bij = aij+min(bi+1j, bi+1j+1)

边值矩形的最优路径
10 30 42 16 34 20 20 22 26 45 42 41 41 24 36 31 39 25 25 67 27 16 27 21 24 32 32 18 12 39 25 40 35 31 39 32 19 22 13 23

边值矩形的最优路径
? 一个n行n列的边值矩 形,每个点可向右或 向下两个方向选择 ? 求左上角到右下角的 路径中,所经过数值 和最大的路径

边值矩形的最优路径
? r54表示横线边值 ? c45表示竖线边值 ? aij表示点ij到右下角的 路径最大值

边值矩形的最优路径
r11 c11 r21 c21 r31 c31 r41 c41 c42 c32 r42 c43 c22 r32 c33 r43 c44 c12 r22 c23 r33 c34 r44 c45 r12 c13 r23 c24 r34 c35 r13 c14 r24 c25 r14 c15

r51

r52

r53

r54

边值矩形的最优路径
a11 c11 a21 c21 a31 c31 r41 a41 c41 a51 a42 c42 r31 r21 r11 a12 c12 a22 c22 a32 c32 r42 a43 c43 r32 r22 r12 a13 c13 a23 c23 a33 c33 r43 a44 c44 r33 r23 r13 a14 c14 a24 c24 a34 c34 r44 a45 c45 r34 r24 r14 a15 c15 a25 c25 a35 c35

r51

a52

r52

a53

r53

a54

r54

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
以下面这个表为例, 某几天的股价是:
天数 股价 1 68 2 69 3 54 4 64 5 68 6 64 7 70 8 67 9 78 10 62 11 98 12 87

这个例子中, 聪明的投资者(按上面的定义),如果每 次买股票时的股价都比上一次买时低,那么他最多 能买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 42

回文词
? 回文词是一种对称的字符串——也就是说,一 个回文词,从左到右读和从右到左读得到的结 果是一样的。任意给定一个字符串,通过插入 若干字符,都可以变成一个回文词。你的任务 是写一个程序,求出将给定字符串变成回文词 所需插入的最少字符数。 ? 比如字符串“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的重量是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背包问题
? Sample Input
11 4 2467 6 10 12 13

? Sample Output 23

单击此处添加标题

单击此处添加段落文字内容

单击此处添加段落文字内容

单击此处添加段落文字内容

单击此处添加段落文字内容

单击此处添加标题

单击此处添加段落文字内容

单击此处添加段落文字内容

单击此处添加段落文字内容

单击此处添加段落文字内容

单击此处添加标题

单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加段落文字内容

单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加段落文字内容

单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加段落文字内容

单击此处添加标题

单击此处添加段落文字内容 单击此处添加段落文字内容

单击此处添加段落文字内容 单击此处添加段落文字内容

单击此处添加段落文字内容 单击此处添加段落文字内容

单击此处添加段落文字内容 单击此处添加段落文字内容

单击此处添加标题

单击此处添加段落文字内容
单击此处添加段落文字内容

单击此处添加段落文字内容
单击此处添加段落文字内容

单击此处添加段落文字内容
单击此处添加段落文字内容

单击此处添加标题

单击此处添加段落文字内容

单击此处添加段落文字内容

单击此处添加段落文字内容

单击此处添加段落文字内容

单击此处添加段落文字内容

单击此处添加段落文字内容

单击此处添加标题
此处添加内容

单击此处添加 段落文字内容

此处添加内容 单击此处添加 段落文字内容

此处添加内容 单击此处添加 段落文字内容

此处添加内容

此处添加内容

此处添加内容

单击此处添加 段落文字内容

单击此处添加 段落文字内容

单击此处添加 段落文字内容

单击此处添加标题

单击添加
单击添加内容文字

单击添加
单击添加内容文字

单击添加
单击添加内容文字

单击添加
单击添加内容文字

单击此处添加标题
单击此处添加段落文字内容
单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加段落文字内容

单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加段落文字内容

单击此处添加段落文字内容 单击此处添加段落文字内容 单击此处添加段落文字内容

单击此处添加段落文字内容

本次课程结束,谢谢欣赏


更多相关文档:

信息学竞赛常用的算法思想讲座之一(动态规划)

信息学竞赛常用的算法思想讲座之一(动态规划) 信息学竞赛常用算法思想信息学竞赛...例如,若选择的子路径(非最短路径)是 3,2,5 (耗费为 9 ),则 1 到 5 ...

动态规划的特点及其应用探讨 信息学竞赛论文

动态规划的特点及其应用探讨 信息学竞赛论文_信息与通信_工程科技_专业资料。目录...动态规划的设计与实现 2.1 动态规划的多样性 2.2 动态规划的模式性 2.3 ...

信息学奥赛——动态规划实例分析及程序实现

全国青少年信息学奥林匹克联赛 动态规划实例分析及程序实现 一、数字三角形 示出...3 9 -1 -1 -1 -1 -1 -1 0 -1 6 5 -1 -1 -1 -1 -1 -1 -...

信息学奥赛动态规划练习

【输入样例】 4 2 4 3 -1 2 【输出样例】 7 81 -1 ---...9 mod 10 = 9 第 1 页共 6 页 石室中学信息学奥赛动态规划练习题目(101211) 整理...

信息学奥赛——树型动态规划的实例分析

信息学奥赛——树型动态规划的实例分析_一年级语文_...实现: 怎么实现,是在竞赛中的很重要的一个问题,...样例输入 7 1 1 1 1 1 1 1 1 3 2 3 6 ...

动态规划习题精讲

【样例输入】 3 456 10 9 11 【样例输出】第 7 页/共 50 页 信息学竞赛中的动态规划专题 199 考虑每一个月,比较当前的工人数 M1 和下一个月所需要的工...

edu_ecologychuanke1477656919

信息学奥赛-动态规划测试讲解课程 5 课时数2课时 在学人数0人价格:¥20.00 立即购买 简介 目录 立即购买 ¥20.00 课程概述 16道测试习题的讲解 在期末作业...

选修课《信息学竞赛》

信息学竞赛》讲义 3.常用的工具软件使用(文字编辑、电子邮件收发等) C.数据...动态规划的思想及基本算法 第 9 页,共 55 页 广州外国语学校第二课堂校本...

3道简单的动态规划

动态规划的问题及源程序动态规划的问题及源程序隐藏>...4 2 1 10 3 3 4 5 7 9 [Copy to clipboard...例如,一朵花的价格是 2 ICU(ICU 是信息学竞赛的...

宜昌市一中青少年奥林匹克信息学联赛提高组试题汇总

动态规划 9页 免费 NOIP实用算法 33页 免费 信息学竞赛题库 3页 免费 宜昌一中第四届NOIP模拟赛... 6页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出...
更多相关标签:
信息学竞赛 | 算法艺术与信息学竞赛 | 奥林匹克信息学竞赛 | 2016安徽省信息学竞赛 | 合肥市信息学竞赛 | 高中信息学竞赛 | 信息学竞赛学什么 | 合肥信息学竞赛 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com