下载文档原格式
第十一讲 动态规划一、动态规划总述动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。
跟分治法一样，动态规划也是通过组合子问题的解而解决整个问题的。
分治法可以把问题划分成一些独立的子问题，递归的求解各个子问题，然后合并子问题的解而得到原问题的解。
与此不同，动态规划适用于子问题不独立的情况，也就是各子问题包含公共的子子问题。
这种情况下，分治法就会有大量的重复计算，即重复求解公共子子问题。
动态规划对每个子子问题只求解一次，将结果存在一张表里，从而避免每次遇到各个子问题时重新计算答案。
动态规划通常应用于最优化问题。
此类问题一般有很多很多种可行解，每个解有一个值，而我们希望找出一个具有最优(最大或最小)值的解。
称这样的解为该问题的最优解（而不是确定的最优解），因为可能存在多个取值最优的解。
动态规划算法的设计可以分为如下4个步骤：1)描述最优解的结构2)递归定义最优解的值，这个递归方程称为状态转移方程3)按自底向上的方式计算最优解的值4)由计算结果构造一个最优解(一般竞赛时无需构造，如果有要求则有时需要在第三步的计算中记录一些附加信息)。
下面介绍一些术语，希望读者在阅读完整节内容后进行理解：阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。
acm培训计划导言ACM (Association for Computing Machinery) 是一个国际性的计算机学会，旨在为计算机专业人士提供交流学习和培训的平台。
ACM 培训计划旨在帮助学生提升他们的算法和编程能力，从而更好地参与 ACM 竞赛。
本培训计划将围绕算法与数据结构、编程语言、数学及竞赛技巧展开，以帮助学生提升专业知识、提高团队合作能力和竞赛技能。
一、培训目标1. 提升学生算法和数据结构基础知识，使其能够灵活运用于解决实际问题。
2. 培养学生对编程语言的深刻理解和应用能力。
3. 加强学生的数学基础，提高解决问题的抽象能力。
4. 提高学生的 ACM 竞赛技巧，培养解决问题的思考和团队合作能力。
二、培训内容1. 算法与数据结构1.1. 基本算法：递归、分治、贪心、动态规划1.2. 基本数据结构：栈、队列、链表、树、图1.3. 高级算法：最短路径、最小生成树、网络流、字符串算法1.4. 算法分析与设计：时间复杂度、空间复杂度和算法优化2. 编程语言2.1. C/C++/Java/Python 等主流编程语言的基本语法和特性2.2. 编程范例分析和练习2.3. 算法实现与调试技巧3. 数学基础3.1. 离散数学基础知识3.2. 数论、组合数学和图论基础3.3. 动态规划数学建模4. ACM 竞赛技巧4.1. ACM 竞赛规则和常见题型分析4.2. 模拟训练和解题技巧分享4.3. 队伍协作与策略分享三、培训方式1. 理论授课1.1. 定期组织专家授课，系统讲解培训内容，由资深ACM 竞赛选手分享解题技巧和经验。
1.2. 组织学习交流会，鼓励学生积极提问和讨论。
2. 实践训练2.1. 组织编程实践训练，引导学生独立完成算法实现和调试。
2.2. 选派导师进行一对一指导，帮助学生解决练习中遇到的难点问题。
3. 竞赛准备3.1. 组织模拟 ACM 竞赛，帮助学生提前适应竞赛环境和节奏。
3.2. 参与区域赛和国际赛前的模拟训练，为学生提供更加真实的竞赛体验。
ACM培训计划书制作人：xxx2008/10/21一、什么是ACMACM/ICPC ( ACM International Collegiate Programming Contest)国际大学生程序设计竞，ACM/ICPC 是由国际计算机界历史悠久、颇具权威性的组织ACM (Association for Computing Machinery ，美国计算机协会) 主办的，世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运用计算机来充分展示自己分析问题和解决问题的能力。
该项竞赛从1970 年举办至今已历31 届，一直受到国际各知名大学的重视，并受到全世界各著名计算机公司的高度关注，在过去十几年中，APPLE 、AT&T 、MICROSOFT 和IBM 等世界著名信息企业分别担任了竞赛的赞助商。
可以说，ACM 国际大学生程序设计竞赛已成为世界各国大学生最具影响力的国际级计算机类的赛事，是广大爱好计算机编程的大学生展示才华的舞台，是著名大学计算机教育成果的直接体现，是信息企业与世界顶尖计算机人才对话的最好机会。
该项竞赛分区域预赛和国际决赛两个阶段进行，各预赛区第一名自动获得参加世界决赛的资格，世界决赛安排在每年的 3 ～ 4 月举行，而区域预赛安排在上一年的9 ～12 月在各大洲举行。
ACM/ICPC 的区域预赛是规模很大、范围很广的赛事。
仅在2003 年参加区域预赛的队伍就有来自75 个国家（地区），1411 所大学的3150 支代表队，他们分别在127 个赛场中进行比赛，以争夺全球总决赛的73 个名额，其激烈程度可想而知。
2004 年第29 届ACM/ICPC 亚洲赛区预赛共设了北京、上海、台北、高雄、汉城、德黑兰、爱媛（日本）、达卡（孟加拉国）、马尼拉、坎普尔（印度）等10 个赛站，来自亚洲各国知名高校的各个代表队进行了激烈的角逐。
中国内地从1996 年开始参加ACM/ICPC 亚洲区预赛，至今已历九届。
ACM-ICPC（重邮赛区）参赛队培训专题计划培训专题及其所占比例：1）搜索：10%2）动态规划：15%3）贪心算法：约5%4）构造：约5%5）图论：约10%6）计算几何：约5%7）纯数学问题：约20%8）数据结构：约5%9）其它：约25%第二次专题——动态规划（1）Jury CompromiseDescriptionIn Frobnia, a far-away country, the verdicts in court trials are determined by a jury consisting of members of the general public. Every time a trial is set to begin, a jury has to be selected, which is done as follows. First, several people are drawn randomly from the public. For each person in this pool, defence and prosecution assign a grade from 0 to 20 indicating their preference for this person. 0 means total dislike, 20 on the other hand means that this person is considered ideally suited for the jury.Based on the grades of the two parties, the judge selects the jury. In order to ensure a fair trial, the tendencies of the jury to favour either defence or prosecution should be as balanced as possible. The jury therefore has to be chosen in a way that is satisfactory to both parties.We will now make this more precise: given a pool of n potential jurors and two values di (the defence's value) and pi (the prosecution's value) for each potential juror i, you are to select a jury of m persons. If J is a subset of {1,..., n} with m elements, then D(J ) = sum(dk) k belong to Jand P(J) = sum(pk) k belong to J are the total values of this jury for defence and prosecution.For an optimal jury J , the value |D(J) - P(J)| must be minimal. If there are several jurys with minimal |D(J) - P(J)|, one which maximizes D(J) + P(J) should be selected since the jury should be as ideal as possible for both parties.Y ou are to write a program that implements this jury selection process and chooses an optimal jury given a set of candidates.InputThe input file contains several jury selection rounds. Each round starts with a line containing two integers n and m. n is the number of candidates and m the number of jury members.These values will satisfy 1<=n<=200, 1<=m<=20 and of course m<=n. The following n lines contain the two integers pi and di for i = 1,...,n. A blank line separates each round from the next. The file ends with a round that has n = m = 0.OutputFor each round output a line containing the number of the jury selection round ('Jury #1', 'Jury #2', etc.).On the next line print the values D(J ) and P (J ) of your jury as shown below and on another line print the numbers of the m chosen candidates in ascending order. Output a blank before each individual candidate number.Output an empty line after each test case.Sample Input4 21 22 34 16 20 0Sample OutputJury #1Best jury has value 6 for prosecution and value 4 for defence:2 3HintIf your solution is based on an inefficient algorithm, it may not execute in the allotted time.（2）Number SequenceDescriptionA single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2...Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another.For example, the first 80 digits of the sequence are as follows: 1121231234123451234561234567123456781234567891234567891012345678910111234567891 0InputThe first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647)OutputThere should be one output line per test case containing the digit located in the position i. Sample Input283Sample Output22（3）CodeDescriptionTransmitting and memorizing information is a task that requires different coding systems for the best use of the available space. A well known system is that one where a number is associated to a character sequence. It is considered that the words are made only of small characters of the English alphabet a,b,c, ..., z (26 characters). From all these words we consider only those whose letters are in lexigraphical order (each character is smaller than the next character).The coding system works like this:• The words are arranged in the increasing order of their length.• The words with the same length are arranged in lexicographical order (the order from the dictionary).• We codify these words by their numbering, starting with a, as follows:a - 1b - 2...z - 26ab - 27...az - 51bc - 52...vwxyz - 83681...Specify for a given word if it can be codified according to this coding system. For the affirmative case specify its code.InputThe only line contains a word. There are some constraints:• The word is maximum 10 letters length• The English alphabet has 26 characters.OutputThe output will contain the code of the given word, or 0 if the word can not be codified.Sample InputbfSample Output55（4）Check the difficulty of problemsDescriptionOrganizing a programming contest is not an easy job. To avoid making the problems too difficult, the organizer usually expect the contest result satisfy the following two terms:1. All of the teams solve at least one problem.2. The champion (One of those teams that solve the most problems) solves at least a certain number of problems.Now the organizer has studied out the contest problems, and through the result of preliminary contest, the organizer can estimate the probability that a certain team can successfully solve a certain problem.Given the number of contest problems M, the number of teams T, and the number of problems N that the organizer expect the champion solve at least. We also assume that team i solves problem j with the probability Pij (1 <= i <= T, 1<= j <= M). Well, can you calculate the probability that all of the teams solve at least one problem, and at the same time the champion team solves at least N problems?InputThe input consists of several test cases. The first line of each test case contains three integers M (0 < M <= 30), T (1 < T <= 1000) and N (0 < N <= M). Each of the following T lines contains M floating-point numbers in the range of [0,1]. In these T lines, the j-th number in the i-th line is just Pij. A test case of M = T = N = 0 indicates the end of input, and should not be processed.OutputFor each test case, please output the answer in a separate line. The result should be rounded to three digits after the decimal point.Sample Input2 2 20.9 0.91 0.90 0 0Sample Output0.972（5）Heroes Of Might And MagicDescriptionIn the new version of the famous game "Heroes of Might and Magic" heroes themselves take active part in battles. More of that, hero can defeat some monsters alone, without any supporting army. In this problem you are asked to develop the program which would find the strategy for a mage hero fighting face to face with a pack of monsters.Each hero initially has HP H hit points and MP H mana points. Heroes can use different spells. Y our hero knows three spells: Lighting Bolt, Teleport and Heal. Each spell costs one mana point.Each monster has HP M hit points. Pack of monsters is a single group of several monsters who act as one. Therefore if initially the pack consists of N M monsters, they have N M × HP M hit points. As the battle proceeds, monsters' number of hit points decreases. If monsters have H hit points, that means that the group consists of ceiling(H / HP M) monsters (ceiling is a function that returns the smallest integer number not less its argument).The battle runs on a one-dimensional battlefield consisting of N + 1 squares, numbered starting from 0. Y our hero resides on the square number 0 and does not move. Monsters initially reside on Nth square and can move. Monsters can move at most V squares a turn.The battle consists of turns. First your hero makes a turn, then the monsters, and so on. Monsters' strategy is very easy - they move in the direction of your hero min(V, P - 1) squares where P is the square number where they were in the beginning of their turn. If the monsters are on the square number 1 in the end of the movement, then they strike your hero. If there are K monsters left in a pack, their strike decreases hit points of the hero by K. If your hero has non-positive hit points, then the hero is defeated.Y our hero's turn is always the casting of some spell. Lighting Bolt spell removes L P hit pointsfrom a pack of monsters, where P is the square number on which the monsters reside. Teleport spell moves monsters to any desired square (except 0 where your hero resides). Heal spell adds dH hit points to hero. However, his hit points never exceed HP H, so if after using Heal spell his hit points are greater then HP H, they are decreased to HP H. If your hero has zero mana points and there is at least one monster left in the pack, then the hero is defeated.Find the strategy which would allow your hero to defeat monsters. Monsters are defeated if their hit points are non-positive.InputThe first line of the input contains positive integer numbers separated by spaces in the following order: N, HP H, MP H, HP M, N M, V, dH. (1 ≤ N ≤ 10, 2 ≤ HP H≤ 100, 1 ≤ MP H≤ 50, 1 ≤ HP M≤ 10, 1 ≤ N M≤ 10, 1 ≤ V ≤ N, 1 ≤ dH < HP H). The second line of the input file contains N integer numbers L1, L2, ..., L N(1 ≤ LP ≤ 10), separated by spaces.OutputIf the hero cannot win the battle, write the word DEFEA TED on the first line of the output. In the other case write the word VICTORIOUS on the first line of the output file and then write any sequence of hero's actions that leads to victory, where each line of the output file starting from the second one must correspond to one hero's turn. The first character of the line must be one of the following:∙L - Cast Lighting Bolt spell.∙T - Cast Teleport spell.∙H - Cast Heal spell.If the hero casts Teleport spell then T character must be followed by a space and an integer number from 1 to N - the square number where the monsters should be teleported to.Sample Input1 6 5 1 4 1 31Sample OutputVICTORIOUSLLHLL。
实用标准文案ACM培训大纲基础内容：数据结构——》搜索——》图论DP数论博弈中级内容数据结构网络流第一章搜索1.二分搜索三分搜索2.栈 3.队列 4.深搜 5.广搜 6.第二章数据结构1.优先队列并查集 2.二叉搜索树3.线段树（单点更新） 4.Trie5.精彩文档．实用标准文案第三章图论1.图的表示1.1二维数组1.2邻接表1.3前向星2.图的遍历2.1双连通分量2.2拓扑排序3.最短路3.1迪杰斯特拉3.2弗洛伊德3.3SPFA4.匹配匈牙利算法5.生成树6.网络流简介第四章动态规划1.状态转移方程2.引入2.10-1背包2.2硬币问题2.3矩阵链乘3.区间DP4.按位DP5.树形DP6.状压DP第五章数论1.欧几里得扩展欧几里得 2.因数分解3.费马小定理 4.欧拉定理 5.素数6.6.1筛法6.2素数判定6.2.1O(√n)方法精彩文档．实用标准文案6.2.2Miller-rabin测试第六章博弈1.Nim和2.SG函数第七章中级数据结构1.树状数组RMQ 2.KMP3.AC自动机4.线段树（区间更新）5.第八章图论进阶1.网络流问题精彩文档．实用标准文案综述在很多人眼里，东北大学秦皇岛分校不算是985高校。
所以我们要用自己的能力证明我们有985的实力。
ACM是计算机界认可度最高的一个比赛，可以说只要区域赛有过奖牌，国内任何IT公司没有理由不要。
同时，在高校之中，对一个大学计算机专业的评价，大部分人也会首先看ACM 的水平。
将ACM打出学校，在国内打出一定成绩，对扩大我校影响力很有帮助。
考虑到本校暂时没有进行专题训练的出题能力，专题训练的题目主要从UESTC 2014年集训队专题训练中获取，再加上从别的OJ上找一些题目。
训练的平台设置在华中科技大学的vertual judge上面。
本人将在毕业之前承担培训任务。
在2015学年开始之前，培训计划为每两周一次，中间空闲的时间由大二或者大一熟悉C++的同学给不熟悉C++的同学进行基础的讲解。
