杭电ACM课件(lecture_03)递推

单击此处添加小标题
1
上面的程序有什么问题？
单击此处添加小标题
2
*
*
本类输入解决方案：
C语法：
while(scanf("%d",&n) && n!=0 ) { .. }
01
C++语法：
while( cin >> n && n != 0 ) { .. }
02
*
*
输入_第四类：
以上几种情况的组合
1095源代码
#2022
*
*
解决办法：
{ . ut << ans << endl << endl; }
C++语法：
02
{ .. printf("%d\n\n",ans); }
C语法：
01
*
*
输出_第三类：
一个Input Block对应一个Output Block，Output Block之间有空行。 参见：HDOJ_1096
*
*
单击此处添加副标题
计算机学院 刘春英
ACM 程序设计
*
*
单击此处添加副标题
ACM入门
第一讲
*
*
单击此处添加副标题
202X
初识ACM
*
*
What is ACM ?
ACM (Association for Computing Machinery) 成立于计算机诞生次年，是目前计算机学界中历史最悠久、最具权威性的组织…
*
*
输入_第五类：
202X

（8－2）
2019/3/10
7
母函数定义：

对于序列a0，a1，a2，…构造一函数：

称函数G(x)是序列a0，a1，a2，…的 母函数
2019/3/10
8
For example:
(1+x)n是序列C(n,0),C(n,1),...,C(n,n)的 母函数。 如若已知序列a0，a1，a2，…则对应 的母函数G(x)便可根据定义给出。 反之，如若已经求得序列的母函数G(x)， 则该序列也随之确定。 序列a0，a1，a2，…可记为{an} 。
2019/3/10 9
实例分析
2019/3/10
10
例1：若有1克、2克、3克、4克的砝码各一 枚， 能称出哪几种重量？各有几种可能方案？
如何解决这个问题呢？考虑构造母函数。 如果用x的指数表示称出的重量，则： 1个1克的砝码可以用函数1+x表示， 1个2克的砝码可以用函数1+x2表示， 1个3克的砝码可以用函数1+x3表示， 1个4克的砝码可以用函数1+x4表示，
可以看出： x2项的系数a1a2+a1a3+...+an-1an中所有的项包括n个 元素a1，a2， …an中取两个组合的全体； 同理：x3项系数包含了从n个元素a1，a2， …an中取3 个元素组合的全体； 以此类推。
2019/3/10 6
特例：
若令a1=a2= …=an=1，在（8-1）式中 a1a2+a1a3+...+an-1an项系数中每一个组合 有1个贡献，其他各项以此类推。故有：
2019/3/10
11
几种砝码的组合可以称重的情况，可 以用以上几个函数的乘积表示：

• dp[2] = dp[1] + 1 + 1 = 4
• dp[3] = min{ dp[1] + 1 * 2 + 1, dp[2] + 1 + 1}
•
=5
G Islands
• 给定最多100个点的有向图，问有多少种加 边的方式，可以让最后整个图只由一些环 构成，没有多余的边。一个环至少要两个 点。
Lecture III 赛题解析
杭航@ZJU mailto:Hang.Hang.ZJU@
QQ:54621399
Part I The 10th ZJU Programming Contest
概述
• A Clock
472/614
• B CAPTCHA
87/399
• C Runaway t Bulb
• 三分法 • 求单峰函数在(x1,x2)上的极值 • 令a=(x2-x1)/3 + x1 • 令b=(x2-x1)/3 *2 + x1 • 如果f(a)>f(b)，则用b更新x2 • 如果f(a)<f(b)，则用a更新x1 • 每次把区间缩小成原来的2/3，最后收敛到
B Light Bulb
• 方法一：数学解法，列出函数式子，求导 解决
• 方法二：猜测L是关于某个参数的单峰函数， 可以采用三分法。
B Light Bulb
• 二分法 • 求单调函数在(x1,x2)上的零点 • 令x=(x1+x1)/2 • 如果f(x)和f(x1)同号，则用x更新x1 • 如果f(x)和f(x2)同号，则用x更新x2 • 每次把区间缩小成原来的1/2，最后收敛到
H Break Out
• 预处理后，变成了一个背包问题，背包的 容量最多为200，有最多200个物品，每个 物品不同容量的时候有不同的价值，求使 得总价值最高的方案。

1001: Buy the TicketProblem DescriptionThe "Harry Potter and the Goblet of Fire" will be on show in the next few days. As a crazy fan of Harry Potter, you will go to the cinema and have the first sight, won’t you?Suppose the cinema only has one ticket-office and the price for per-ticket is 50 dollars. The queue for buying the tickets is consisted of m + n persons (m persons each only has the 50-dollar bill and n persons each only has the 100-dollar bill).Now the problem for you is to calculate the number of different ways of the queue that the buying process won't be stopped from the first person till the last person.Note: initially the ticket-office has no money.The buying process will be stopped on the occasion that the ticket-office has no 50-dollar bill but the first person of the queue only has the 100-dollar bill.InputThe input file contains several test cases. Each test case is made up of two integer numbers: m and n. It is terminated by m = n = 0. Otherwise, m, n <=100.OutputFor each test case, first print the test number (counting from 1) in one line, then output the number of different ways in another line.Sample Input3 03 13 30 0Sample OutputTest #1:6Test #2:18Test #3:180SourceHUANG, Ninghai题目分析：题目大意：电影院买票，收银台没有零钱，而排队买票的人手里拿着的都是100元或是50元，每张票50元，给出拿100或50的各自人数，求出有几种排列方法使得收银台不会因找不出钱而停止！我的思路：设m张50元n张100元时的排列方法有f(m,n)种，总人数为m+n；当总人数为m+n-1时，有两种情况：（1）m少1。