北京大学ACM国际大学生程序设计竞赛课件8

{ f(i,j)=
f(i-1,j-1)+1 (a[i]==b[j]) max(f(i-1,j),f(i,j-1)) (a[i]!=b[j])
由于f(i,j)只和f(i-1,j-1), f(i-1,j)和f(i,j-1)有 关, 而在计算f(i,j)时, 只要选择一个合适 的顺序, 就可以保证这三项都已经计算出 来了, 这样就可以计算出f(i,j). 这样一直 推到f(len(a),len(b))就得到所要求的解了.
29 2020/5/11
二、动态规划的基本步骤
动态规划算法通常用于求解具有某 种最优性质的问题。在这类问题中，可 能会有许多可行解。每一个解都对应于 一个值，我们希望找到具有最优值（最 大值或最小值）的那个解。设计一个动 态规划算法，通常可以按以下几个步骤 进行：
30 2020/5/11
（1）找出最优解的性质，并刻画其结构特征。 （2）递归地定义最优值。 （3）以自底向上的方式计算出最优值。 （4）根据计算最优值时得到的信息，构造一个
f[i] = max(f[i], f[j]+1) (1<=j<i，且Mice[i].W> Mice[j].W，Mice[i].S < Mice[j].S)
其中，初始条件为f[i]=1 (i=1, 2, ..., n)。
20 2020/5/11
Qestion:
两个问题有本 质区别吗？
21 2020/5/11
为(n-2)*2=4,而另外两条直线既可能平行也可能相交，因此可能交点
数为：
（n-2）*2+0=4 或者
(n-2)*2+1=5
4、 第四条直线不与任何一条直线平行，交点数为：
(n-3)*3+0=3 或者 (n-3)*3+2=5 或者 (n-3)*3+3=6

Problem
Conqueror's batalion
Table of Contents
The problem Solution
The problem
CENTRAL EUROPEAN OLYMPIAD IN INFORMATICS
30 June – 6 July 2002 Day 1: conquer Conqueror's battalion Time limit: 1 s Memory limit: 16 MB
The problem
If at least one of your soldiers reaches the uppermost stair, you will be the winner, in the other case, you will be the loser.
The problem
The problem
In case the game ends (either because you won or there are no more soldiers in the game), the library will terminate your program correctly. Your program may not terminate in any other way.
The problem
For each stair, you are given the number of soldiers standing on it, with number 1 being the uppermost stair and N the bottom one. None of your soldiers stands on stair 1 at the beginning.

第一章
算法设计常用到的基本策略
程序的灵魂
数据结构+算法=程序 算法设计思想 算法分析：从时空、适用范围来分析，重点考
虑时间效率和空间开销 复杂度分析 复杂度等级：多项式算法、指数级算法 五个重要的策略：
一 对应的策略
将问题对应成另一个易于思考的问题 A问题->B问题 B有现成算法，从而求解
<算法设计与分析>课程学习方法
1. 课堂精讲，课外多练，参考题解，精做（解 题）报告，提高程序设计能力，提高程序调 试能力，提高算法分析和优化能力;
2. 基本作业： SICILY上完成指定题目，完成典 型题目的解题报告
<算法设计与分析>课程学习方法
3.考试：ACM方式,网上自动测评,诚信是IT人立足之本! CS： (04级175人:10题2人, 9题
人,8:2,7:4,6:19,5:19,4:30,3:24,2:53, 1:8,0:11； 05级99人：8题2人，7题3人，6题2人，5题2人，4 题
8人，3题15人，2题35人，1题21人，0题11人; 06级105人：7题5人，6题3人，5题9人，4 题16人，3
题33人，2题16人，1题14人，0题11人) SS：06、07级185人（ 7题4人，6题3人，5题4人，4
题3人，3题21人，2题41人，1题52人，0题57人）
<算法设计与应用>课程学习方法
Cs07:178人 8题1人，7题5人，6题10人，5题24人，4 题53人，3题31人，2题28人，1题14人，0题12人;
3.作业扩展内容：中大OJ 、国内OJ,每周一赛题目; 4.主要OJ:
Poj : http://
一 对应的策略

10
2013-7-25
解法
#include <stdio.h> int main() { int n,sum; int i; int a; while(scanf("%d",&n)!=EOF&&n!=0){ sum = 0; a = 0; for(i = 0;i < n;i++){ scanf("%d",&a); sum += a; } printf("%d\n",sum); } return 0; }
共用体变量的引用方式 只有先定义了共用体变量才能引用它，而且不能引用共 用体变量，而只能引用共用体变量中的成员

例如:前面定义了a、b、c为共用体变量
a.i （引用共用体变量中的整型变量ｉ） a.ch（引用共用体变量中的字符变量ｃｈ） a.f （引用共用体变量中的实型变量ｆ）
32
共用体
22
结构体变量的引用
引用结构体变量中成员的方式为 结构体变量名.成员名 例 如 ， student1.num表 示student1 变量中的 num成员,即student1的num(学号)项。可以对变 量 的 成 员 赋值 , 例 如 :student1.num=10010;“.” 是成员(分量)运算符,它在所有的运算符中优先 级最高,因此可以把student1.num作为一个整体 来看待。上面赋值语句的作用是将整数10010赋 给student1变量中的成员num。
87.5 Beijing
100101 Li Fun
17
概述
声明一个结构体类型的一般形式为： struct 结构体名 ｛成员表列｝； 结构体名

OLE (Output Limit Exceed) 输出超界 (一般 不太常见，除非你输出了超过 1024K ...)
DP (Dynamic Programming) 动态编程，动 态规划
DFS (Depth First Search) 深度优先搜索
BFS (Breadth First Search) 宽度/广度优先搜 索
输入输出
%d %lld %lf自动扫描前导空格 比如：读入5个整数到A[5]
输入文件中，数的排布是这个样子
35 26 78
99
206
不管它，直接5次%d
for ( int i = 0; i < 5; i++ ) scanf(“%d”, A + i);
%lld用于输入和输出长整数(long long,64位) %lf用于输入输出double
cout<<"j="; printf("%d\n", j); } return 0; }
0
1
j=0 j=1 j=2 j=3
2 3 4 j=j=j=j=j=
j=4
输入输出
scanf
输入格式
%d %lld %c %s %lf
对每种格式搞清楚一个重要问题
是否自动跳过前导空白？
什么是空白：空格，TAB，回车
输入输出
%s 读一个字符串，自动扫描前导空白，读到 空白结束
如： abcd efgh，将读出”abcd”
%c读一个字符，但是不扫描前导空白
如何读一个非空白字符呢？
比如，读取某人的信息，其性别用M/F表示
TopBoy M ComputerScience
Kitty

ACM程序设计
上一周，
你
了吗？
2020/1/10
2
每周一星（7）：
07054202
2020/1/10
3
第八讲
母函数及其应用
（Generation function）
2020/1/10
4
从递推关系说起
2020/1/10
5
研究以下多项式乘法：
(8－1)
可以看出：
x2项的系数a1a2+a1a3+...+an-1an中所有的项包括n个元 素a1，a2， …an中取两个组合的全体； 同理：x3项系数包含了从n个元素a1，a2， …an中取3 个元素组合的全体；
HDOJ_1398 Square Coins
Sample Input 2 10 30 0
Sample Output 1 4 27
2020/1/10
19
算法分析：
典型的利用母函数可解的题目。
G(x)=(1+x+x2+x3+x4+…)(1+x4+x8+x12 +…)(1+x9+x18+x27+…)…
2020/1/10
以此类推。
2020/1/10
6
特例：
若令a1=a2= …=an=1，在（8-1）式中 a1a2+a1a3+...+an-1an项系数中每一个组合有 1个贡献，其他各项以此类推。故有：
（8－2）
2020/1/10
7
母函数定义：
对于序列a0，a1，a2，…构造一函数：
称函数G(x)是序列a0，a1，a2，…的 母函数

2020/10/21
10
如何排名？
首先根据解题数目进行排名。 如果多支队伍解题数量相同，则根据总用时加上惩
罚时间进行排名。 总用时和惩罚时间由每道解答正确的试题的用时加
上惩罚时间而成。 每道试题用时将从竞赛开始到试题解答被判定为正
确为止，其间每一次错误的运行将被加罚20分钟时 间，未正确解答的试题不记时。
州）；
2020/10/21
7
ACM in XTU
2004年，第一次参加亚洲区预选赛（网络预赛） 2005～2011，每年10月左右——
湖南省第1～6届大学生程序设计竞赛 2004～2010，每年10~12月——
第29～35届ACM国际大学生程序设计竞赛 亚洲区预选赛
2020/10/21
8
预期赛事（今后每年）
校程序设计竞赛
个人编程能力的比拼 中文或者英文题目，考察编程基本功
2020/10/21
13
ACM队队员的基本原则
基本要求
人品好 愿意花时间在这项赛事上 有团队合作精神
能力要求
程序设计 英语科技文献阅读
数学
2020/10/21
14
开课目的
为湘大ACM代表队培养后备人才 提高分析问题和应用计算机编程解决
ACM
第一讲
ACM入门
(Introduction to ACM)
2020/10/21
2
第一部分
ACM简介
2020/10/21

What is ACM ?
ACM-(Association for Computing Machinery)
成立于计算机诞生次年，是目前计算 机学界中历史最悠久、最具权威性的 组织…

ACM程序设计大赛
9
最常见题型
Dynamic Programming(动态规划) Greedy(贪心) Complete Search(穷举) Flood Fill (种子填充) Shortest Path (最短路径) Recursive Search Techniques (回溯） Minimum Spanning Tree （最小生成树） Knapsack（背包） Computational Geometry(计算几何) Network Flow(网络流) Eulerian Path (欧拉回路) Two-Dimensional Convex Hull (二维凸包) BigNums (大数) Heuristic Search(启发式搜索) Approximate Search (近似搜索) Ad Hoc Problems(杂题)
ACM程序设计大赛
10
ACM程序设计大赛
11
离散数学第1讲 命题逻辑基础
数理逻辑将能够判断真假的陈述句称作命题。 命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字 表示，如Ai，R等，例如： A1：我是一名大学生。 联结词： 合取联结词： 析取联结词： 否定联结词： 蕴涵联结词： 等价联结词： 逻辑真值： 0，1
16
命题的翻译： 例：假如上午不下雨，我去看电影，否则就在家里读书或看报。 解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S： 我在家里看报。 本例可表示为： （PQ）∧（P（R∨S））。
ACM程序设计大赛
17
命题公式的解释：
定义 设P1，P2，…，Pn是出现在命题公式G中的全部命题变 元，指定P1，P2，…，Pn的一组真值，称这组真值为G的 一个解释或赋值，记作I，公式G在I下的真值记作TI （G）。 例如，G=（P∧Q）R，则I： P Q R 1 1 0 是G的一个解释，在这个解释下G的真值为1，即TI（G）=1。

22
for (w=G->first(v); w<G->n(); w = G>next(v,w))
if (G->getMark(w) == UNVISITED) { G->setMark(w, VISITED); Q->enqueue(w); }
PostVisit(G, v); // Take action }}
Q Q
31
() ((1,1)) ((1,1) (2,3)) ((1,1) (2,4)) ((1,1) (2,4) (3.2))
Q Q
Q
32
() ((1,1)) ((1,1) (2,3)) ((1,1) (2,4)) ((1,1) (2,4) (3.2))
Q Q
33
Q () ((1,1)) ((1,1) (2,3)) ((1,1) (2,4)) ((1,1) (2,4) (3.2))
求解算法
穷举法 贪心法 深度/广度优先搜索
图和树的搜索 回溯法（深度优先）
递归
分治
动态规划法
55
谢谢！
56
49
动态规划法的思想
自底向上构造 在原问题的小子集中计算 每一步列出局部最优解，并用一张
表保留这些局部最优解，以避免重 复计算 子集越来越大，最终在问题的全集 上计算，所得出的就是整体最优 解。
50
Fib(1)=Fib(2)=1
Fibonacci数列 Fib(n)=Fib(n-1) + Fib (n-2)
23
八数码 深度优先搜索
1
23 184 765
2
c
3
283 164 75
283 14 765