算法集训队作用

A. 高中才开始学习信息竞赛有机会进入国家集训队吗

我从小六开始学，一直到初三前都没怎么学，大概都是在搞文化课(不过搞得也差)，基本没有提升，oi省内排名也一直在50+左右徘徊。
初三的时候一冲动就搞了一两个月停课训练，noip570，然后进了b队，签了t大一本，最终noi2017rank38.

高中生搞竞赛停课的话，训练的效率应当是比初中生每天颓废摸鱼要高的多的，况且我也算比较弱也比较颓废的(严重的时候一天一个多小时训练时间全部在颓)，真正有实力也勤奋的大佬认真搞一年应该顶我初中瞎搞三年(比如今年的zzx大佬)。

所以不但有机会，而且机会还挺大的。

B. 全世界最强的算法平台codeforces究竟有什么魅力

简单介绍一下codeforces这个网站，codeforces位于宇宙编程最强的毛国。据说最早是由俄罗斯的一群大学生维护的，它最大的特点就是代码和题解的公开。所有人都可以随意查看其它大牛的代码，可以说是非常具有开源精神了。

codeforces很大的特点就是题目兼容并蓄，什么难度等级的题目都可以找到。并且题目很有意思，往往思维陷阱比较多，也就是思维题比较多。对于数据结构以及算法的考察相对弱一些，更多的时候往往是告诉你用什么算法你也不知道怎么做……

codeforces另外一个很大的特点就是它有自己的上分系统，基本上每周会举办一到两次在线的算法比赛。一般的比赛时长是两个小时，只要注册账号就可以免费参加。我记得当年第一次参加比赛会获得一个初始分是1500，然后根据你在比赛当中的表现上分或者减分。由于参加的选手水平实力强度不一，所以它开设了好几个档次(div)，不同层次的选手面对的题目难度也不一样，这样保证了大家都可以愉快地参赛。

codeforces在比赛的时候只会测试一小部分数据，真正的测试集会放到赛后进行测试。所以在比赛中测试通过的代码，只是通过了小数据验证，很有可能有隐藏的问题没被发现。当你通过了这道题之后，你就可以去查看其他通过人的代码，去分析它们有没有问题，如果发现了bug，可以构造一份数据hack掉他的提交。hack成功之后，你会获得分数的奖励。

你可以双击打开其他人的提交记录，去阅读他们的代码。到了比赛后期，能做的问题做的差不多了之后，就进入了紧张刺激的互相hack阶段。讲道理，这比只是单纯做题的竞赛要有趣多了。

以前我们acm集训队经常晚上一起打codeforces的比赛，有时候看到队友在一个房间里，还会互相关注一下近况，互相hack一把，不得不说现在怀念起来还是非常有意思的。

好了，关于codeforces网站就介绍到这里了，如果你也对算法感兴趣的话，不妨试着用一下它吧，相信你也会找到算法的乐趣。

C. 进入acm协会能学到什么

哈，我就是acm校集训队的同学~~

具体的，算法，数据结构知识都会学的很深刻，起码比计算机专业的非acm的同学，强很多了。
然后，代码能力的提升，也是非常非常大的。认认真真做过acm的同学就会有体会，写个代码要比没做过的容易得多，而且效率高。
再有就是团队配合，三人组队赛，配合很重要的，你们之间会有默契，以后做什么事情都会很顺利的~~

最主要的，计算机专业招聘去IT企业，笔试面试的时候都会有算法题，这个做过acm的是非常吃香的，没做过的只能干瞪眼了~~

D. 参加acm需要学什么

其实acmer们都是自己训练的啊，这种东西只能自己学哈~先从基本的开始吧，把c/c++练熟了，java要掌握一些。然后就是算法上的东西了。算法的学习是比较痛苦的，书建议看算法导论，算法艺术与信息学竞赛，具体数学，柔性字符串匹配，然后是去各大oj上训练做题，推荐poj，zoj，hdoj，还有各种比赛。下面是详细的训练方法~

训练方法。现在这个赛季基本就算结束了，所以可以从自身能力开始提升，先把算法掌握的全面一些。模拟，数学，计算几何，图论，数据结构，动态规划，搜索，字符串匹配，贪心，这些知识都要进行学习。如果来不及的话，尽量保证，每一块知识都能有两个人覆盖到，这样三人组队，可以保证稳定发挥。个人训练可以自己做题，按各个知识点来。也可以穿插着去做做比赛，topcoder的srm和codeforces都很不错，还有zoj的月赛。这都是平时练习的好机会。

比赛前一两个月，要进行队伍磨合。组队做一些比赛，可以去hust的oj上自己挂比赛。注意分配几时，然后读题要仔细，分题的时候要清醒，千万别觉得这个题可做，就直接搞，一定要和队友商量。卡题的时候，切记不要冲动，乱交会导致罚时飙升啊，那样很痛苦的。

然后热身赛记得测一下longlong类型的输出是用lld还是I64d，然后放平心态就可以了~

E. 一个计算机专业大学生，如何看待学校的ACM集训队我不懂为什么那么多人挤破脑袋想加入我觉得一名优

啥？居然有很多人想挤破脑袋进ACM集训队这样的事情。。。。。
估计是因为很多人盲目的把ACM看待为高中时候数学化学竞赛的性质的原因吧。。。
以我的经历来看，计算机算法竞赛对人的成长作用毫无疑问是不可估量的，但这绝不同于高中时那些竞赛的性质。选择ACM不是说是为了锻炼，更不可能是为了证书（普通比赛的证书随便一大把，但想拿到有影响力的证书简直是难的可怕）。选择ACM就意味着你选择了你以后的道路，为什么这么说呢，其一，研究算法是一项极其需要脑力和时间的事情，这就意味着你必须要放弃其他许多事情，只能专其一，尽管ACM跟NOI相比跟侧重于运用而不是创新；其二，可以说：一入此门深似海。。。这会彻底颠覆你以前思考问题的模式，学会并习惯一种全新的的思维模式。
这就是我自己亲身经历的体会，你必须有极大的兴趣才能坚持的下来（比如你很多时候会对着电脑查BUG 10+小时或者一道题目要近一个月才想通），所以我敢说那些挤破脑袋想加入的95%的人会很快就放弃

F. 求助：学校太烂，好像没有集训队，怎么参加acm

应该是没有蹭别的学校的名额参加acm的~要组队的话，还是找自己学校的人组~如果学校支持的话最好，不支持的话，就很困难了~如果数学好的话对搞acm肯定是有帮助的，但也不是绝对的，原先的acm比赛偏向算法，搞得像是OI的加强版~现在的话越来越偏重对编码能力的要求~现在赛制是先参加各个赛区的网络赛预赛（网络赛是没有参赛限制的，只要能凑到3个人就行），再参加区域赛，再参加世界总决赛，亚洲一共15个赛区，中国大陆5个，每年的9月到11月是各大洲的区域赛，网络预赛一般在区域赛前两三个星期比的~过了网络赛才有参加区域赛现场赛的资格~网络赛的时候竞争就挺激烈的了~搞acm跟大学的好坏没决定性的关系，主要是看学校的重视程度，每年都有一些非211高校进世界总决赛的~好好努力吧~

G. 中专集训队有必要进吗

有必要。集训后可参加中职技能大赛。对中职学生考查本专业比较具有代表性的技能，能够一定程度上反映社会对职业院校学生能力的要求，通过参加技能大赛，可以全面发展专业技能，提升专业素养，对以后在大学之后专业技能的学习具有较强的促进作用。

H. acm初学者要准备什么 看什么书啊

刚刚接触信息学领域的同学往往存在很多困惑，不知道从何入手学习，在这篇文章里，我希望能将自己不多的经验与大家分享，希望对各位有所帮助。
一、语言是最重要的基本功

无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当不利的。其实，笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维，因为对于小程序来说这不旦需要花费更多的时间去编写代码，也会降低程序的执行效率。

接着说C和C++。许多现在参加讲座的同学还在上大一，C的基础知识刚刚学完，还没有接触过C++，其实在赛场上使用纯C的选手还是大有人在的，它们主要是看重了纯C在效率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只要提高了自己在算法设计上的造诣，纯C一样能发挥巨大的威力。

而C++相对于C，在输入输出流上的封装大大方便了我们的操作，同时降低了出错的可能性，并且能够很好地实现标准流与文件流的切换，方便了调试的工作。如果有些同学比较在意这点，可以尝试C和C++的混编，毕竟仅仅学习C++的流操作还是不花什么时间的。

C++的另一个支持来源于标准模版库（STL），库中提供的对于基本数据结构的统一接口操作和基本算法的实现可以缩减我们编写代码的长度，这可以节省一些时间。但是，与此相对的，使用STL要在效率上做出一些牺牲，对于输入规模很大的题目，有时候必须放弃STL，这意味着我们不能存在“有了STL就可以不去管基本算法的实现”的想法；另外，熟练和恰当地使用STL必须经过一定时间的积累，准确地了解各种操作的时间复杂度，切忌对STL中不熟悉的部分滥用，因为这其中蕴涵着许多初学者不易发现的陷阱。

通过以上的分析，我们可以看出仅就信息学竞赛而言，对语言的掌握并不要求十分全面，但是对于经常用到的部分，必须十分熟练，不允许有半点不清楚的地方，下面我举个真实的例子来说明这个道理——即使是一点很细微的语言障碍，都有可能酿成错误：

在去年清华的赛区上，有一个队在做F题的时候使用了cout和printf的混合输出，由于一个带缓冲一个不带，所以输出一长就混乱了。只是因为当时judge team中负责F题的人眼睛尖，看出答案没错只是顺序不对（答案有一页多，是所有题目中最长的一个输出），又看了看程序发现只是输出问题就给了个Presentation error（格式错）。如果审题的人不是这样而是直接给一个 Wrong Answer，相信这个队是很难查到自己错在什么地方的。

现在我们转入第二个方面的讨论，基础学科知识的积累。

二、以数学为主的基础知识十分重要

虽然被定性为程序设计竞赛，但是参赛选手所遇到的问题更多的是没有解决问题的思路，而不是有了思路却死活不能实现，这就是平时积累的基础知识不够。今年World Final的总冠军是波兰华沙大学，其成员出自于数学系而非计算机系，这就是一个鲜活的例子。竞赛中对于基础学科的涉及主要集中于数学，此外对于物理、电路等等也可能有一定应用，但是不多。因此，大一的同学也不必为自己还没学数据结构而感到不知从何入手提高，把数学捡起来吧！下面我来谈谈在竞赛中应用的数学的主要分支。

1、离散数学——作为计算机学科的基础，离散数学是竞赛中涉及最多的数学分支，其重中之重又在于图论和组合数学，尤其是图论。

图论之所以运用最多是因为它的变化最多，而且可以轻易地结合基本数据结构和许多算法的基本思想，较多用到的知识包括连通性判断、DFS和BFS，关节点和关键路径、欧拉回路、最小生成树、最短路径、二部图匹配和网络流等等。虽然这部分的比重很大，但是往往也是竞赛中的难题所在，如果有初学者对于这部分的某些具体内容暂时感到力不从心，也不必着急，可以慢慢积累。

竞赛中设计的组合计数问题大都需要用组合数学来解决，组合数学中的知识相比于图论要简单一些，很多知识对于小学上过奥校的同学来说已经十分熟悉，但是也有一些部分需要先对代数结构中的群论有初步了解才能进行学习。组合数学在竞赛中很少以难题的形式出现，但是如果积累不够，任何一道这方面的题目却都有可能成为难题。

2、数论——以素数判断和同余为模型构造出来的题目往往需要较多的数论知识来解决，这部分在竞赛中的比重并不大，但只要来上一道，也足以使知识不足的人冥思苦想上一阵时间。素数判断和同余最常见的是在以密码学为背景的题目中出现，在运用密码学常识确定大概的过程之后，核心算法往往要涉及数论的内容。

3、计算几何——计算几何相比于其它部分来说是比较独立的，就是说它和其它的知识点很少有过多的结合，较常用到的部分包括——线段相交的判断、多边形面积的计算、内点外点的判断、凸包等等。计算几何的题目难度不会很大，但也永远不会成为最弱的题。

4、线性代数——对线性代数的应用都是围绕矩阵展开的，一些表面上是模拟的题目往往可以借助于矩阵来找到更好的算法。

5、概率论——竞赛是以黑箱来判卷的，这就是说你几乎不能动使用概率算法的念头，但这也并不是说概率就没有用。关于这一点，只有通过一定的练习才能体会。

6、初等数学与解析几何——这主要就是中学的知识了，用的不多，但是至少比高等数学多，我觉得熟悉一下数学手册上的相关内容，至少要知道在哪儿能查到，还是必要的。

7、高等数学——纯粹运用高等数学来解决的题目我接触的只有一道，但是一些题目的叙述背景往往需要和这部分有一定联系，掌握得牢固一些总归没有坏处。

以上就是竞赛所涉及的数学领域，可以说范围是相当广的。我认识的许多人去搞信息学的竞赛就是为了逼着自己多学一点数学，因为数学是一切一切的基础。

三、数据结构与算法是真正的核心

虽然数学十分十分重要，但是如果让三个只会数学的人参加比赛，我相信多数情况下会比三个只会数据结构与算法的人得到更为悲惨的结局。

先说说数据结构。掌握队列、堆栈和图的基本表达与操作是必需的，至于树，我个人觉得需要建树的问题有但是并不多。（但是树往往是很重要的分析工具）除此之外，排序和查找并不需要对所有方式都能很熟练的掌握，但你必须保证自己对于各种情况都有一个在时间复杂度上满足最低要求的解决方案。说到时间复杂度，就又该说说哈希表了，竞赛时对时间的限制远远多于对空间的限制，这要求大家尽快掌握“以空间换时间”的原则策略，能用哈希表来存储的数据一定不要到时候再去查找，如果实在不能建哈希表，再看看能否建二叉查找树等等——这都是争取时间的策略，掌握这些技巧需要大家对数据结构尤其是算法复杂度有比较全面的理性和感性认识。

接着说说算法。算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。这里要说的是，有些初学者在学习这些搜索基本算法是不太注意剪枝，这是十分不可取的，因为所有搜索的题目给你的测试用例都不会有很大的规模，你往往察觉不出程序运行的时间问题，但是真正的测试数据一定能过滤出那些没有剪枝的算法。实际上参赛选手基本上都会使用常用的搜索算法，题目的区分度往往就是建立在诸如剪枝之类的优化上了。

常用算法中的另一类是以“相似或相同子问题”为核心的，包括递推、递归、贪心法和动态规划。这其中比较难于掌握的就是动态规划，如何抽象出重复的子问题是很多题目的难点所在，笔者建议初学者仔细理解图论中一些以动态规划为基本思想所建立起来的基本算法（比如Floyd-Warshall算法），并且多阅读一些定理的证明，这虽然不能有什么直接的帮助，但是长期坚持就会对思维很有帮助。

四、团队配合

通过以上的介绍大家也可以看出，信息学竞赛对于知识面覆盖的非常广，想凭一己之力全部消化这些东西实在是相当困难的，这就要求我们尽可能地发挥团队协作的精神。同组成员之间的熟练配合和默契的形成需要时间，具体的情况因成员的组成不同而不同，这里我就不再多说了。

五、练习、练习、再练习

知识的积累固然重要，但是信息学终究不是看出来的，而是练出来的，这是多少前人最深的一点体会，只有通过具体题目的分析和实践，才能真正掌握数学的使用和算法的应用，并在不断的练习中增加编程经验和技巧，提高对时间复杂度的感性认识，优化时间的分配，加强团队的配合。总之，在这里光有纸上谈兵是绝对不行的，必须要通过实战来锻炼自己。

大家一定要问，我们去哪里找题做，又如何检验程序是否正确呢？这大可不必担心，现在已经有了很多网上做题的站点，这些站点提供了大量的题库并支持在线判卷，你只需要把程序源码提交上去，马上就可以知道自己的程序是否正确，运行所使用的时间以及消耗的内存等等状况。下面我给大家推荐几个站点，笔者不建议大家在所有这些站点上做题，选择一个就可以了，因为每个站点的题都有一定的难易比例，系统地做一套题库可以使你对各种难度、各种类型的题都有所认识。

1、Ural：

Ural是中国学生对俄罗斯的Ural州立大学的简称 ，那里设立了一个Ural Online Problem Set，并且支持Online Judge。Ural的不少题目算法性和趣闻性都很强，得到了国内广大学生的厚爱。根据“信息学初学者之家”网站的统计，Ural的题目类型大概呈如下的分布：

题型
搜索
动态规划
贪心
构造
图论
计算几何
纯数学问题
数据结构
其它

所占比例
约10%
约15%
约5%
约5%
约10%
约5%
约20%
约5%
约25%

这和实际比赛中的题型分布也是大体相当的。有兴趣的朋友可以去看看。

2、UVA：

UVA代表西班牙Valladolid大学(University de Valladolid)。该大学有一个那里设立了一个PROBLEM SET ARCHIVE with ONLINE JUDGE ，并且支持ONLINE JUDGE，形式和Ural大学的题库类似。不过和Ural不同的是，UVA题目多的多，而且比较杂，而且有些题目的测试数据比较刁钻。这使得刚到那里做题的朋友往往感觉到无所适从，要么难以找到合适的题目，要么Wrong Answer了很多次以后仍然不知道错在那里。 如果说做Ural题目主要是为了训练算法，那么UVA题目可以训练全方位的基本功和一些必要的编程素质。UVA和许多世界知名大学联合办有同步网上比赛，因此那里强人无数，不过你先要使自己具有听懂他们在说什么的素质：）

3、ZOJ：

ZOJ是浙江大学建立的ONLINE JUDGE，是中国大学建立的第一个同类站点，也是最好和人气最高的一个，笔者和许多班里的同学就是在这里练习。ZOJ虽然也定位为一个英文网站，但是这里的中国学生比较多，因此让人觉得很亲切。这里目前有500多道题目，难易分配适中，且涵盖了各大洲的题目类型并配有索引，除此之外，ZOJ的JUDGE系统是几个网站中表现得比较好的一个，很少出现Wrong Answer和Presentation error混淆的情况。这里每月也办有一次网上比赛，只要是注册的用户都可以参加。

说起中国的ONLINE JUDGE，去年才开始参加ACM竞赛的北京大学现在也建立了自己的提交系统；而我们学校也是去年开始参加比赛，现在也有可能推出自己的提交系统，如果能够做成，到时候大家就可以去上面做题了。同类网站的飞速发展标志着有越来越多的同学有兴趣进入信息学的领域探索，这是一件好事，同时也意味着更激烈的竞争。

看看这篇文章对你有什么帮助！我也是ACM初学者！

I. C程序的动态规划是啥意思

【关键词】动态规划 阶段
【摘要】
动态规划是信息学竞赛中的常见算法，本文的主要内容就是分析它的特点。
文章的第一部分首先探究了动态规划的本质，因为动态规划的特点是由它的本质所决定的。第二部分从动态规划的设计和实现这两个角度分析了动态规划的多样性、模式性、技巧性这三个特点。第三部分将动态规划和递推、搜索、网络流这三个相关算法作了比较，从中探寻动态规划的一些更深层次的特点。
文章在分析动态规划的特点的同时，还根据这些特点分析了我们在解题中应该怎样利用这些特点，怎样运用动态规划。这对我们的解题实践有一定的指导意义。
【正文】
动态规划是编程解题的一种重要的手段，在如今的信息学竞赛中被应用得越来越普遍。最近几年的信息学竞赛，不分大小，几乎每次都要考察到这方面的内容。因此，如何更深入地了解动态规划，从而更为有效地运用这个解题的有力武器，是一个值得深入研究的问题。
要掌握动态规划的应用技巧，就要了解它的各方面的特点。首要的，是要深入洞悉动态规划的本质。
§1动态规划的本质
动态规划是在本世纪50年代初，为了解决一类多阶段决策问题而诞生的。那么，什么样的问题被称作多阶段决策问题呢？
§1.1多阶段决策问题
说到多阶段决策问题，人们很容易举出下面这个例子。
[例1] 多段图中的最短路径问题：在下图中找出从A1到D1的最短路径。
仔细观察这个图不难发现，它有一个特点。我们将图中的点分为四类（图中的A、B、C、D），那么图中所有的边都处于相邻的两类点之间，并且都从前一类点指向后一类点。这样，图中的边就被分成了三类（AàB、BàC、CàD）。我们需要从每一类中选出一条边来，组成从A1到D1的一条路径，并且这条路径是所有这样的路径中的最短者。
从上面的这个例子中，我们可以大概地了解到什么是多阶段决策问题。更精确的定义如下：
多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列[1]。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。
从上述的定义中，我们可以明显地看出，这类问题有两个要素。一个是阶段，一个是决策。
§1.2阶段与状态
阶段：将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。常用字母k表示阶段变量。[1]
阶段是问题的属性。多阶段决策问题中通常存在着若干个阶段，如上面的例子，就有A、B、C、D这四个阶段。在一般情况下，阶段是和时间有关的；但是在很多问题（我的感觉，特别是信息学问题）中，阶段和时间是无关的。从阶段的定义中，可以看出阶段的两个特点，一是“相互联系”，二是“次序”。
阶段之间是怎样相互联系的？就是通过状态和状态转移。
状态：各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量，状态变量sk的取值集合称为状态集合，用Sk表示。[1]
状态是阶段的属性。每个阶段通常包含若干个状态，用以描述问题发展到这个阶段时所处在的一种客观情况。在上面的例子中，行人从出发点A1走过两个阶段之后，可能出现的情况有三种，即处于C1、C2或C3点。那么第三个阶段就有三个状态S3={C1,C2,C3}。
每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为状态转移（暂不定义）。上例中C3点可以从B1点过来，也可以从B2点过来，从阶段2的B1或B2状态走到阶段3的C3状态就是状态转移。状态转移是导出状态的途径，也是联系各阶段的途径。
说到这里，可以提出应用动态规划的一个重要条件。那就是将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的发展，而只能通过当前的这个状态。换句话说，每个状态都是“过去历史的一个完整总结[1]”。这就是无后效性。对这个性质，下文还将会有解释。
§1.3决策和策略
上面的阶段与状态只是多阶段决策问题的一个方面的要素，下面是另一个方面的要素——决策。
决策：当各段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。表示决策的变量，称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合。常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。显然有uk(sk) ÎDk(sk)。[1]
决策是问题的解的属性。决策的目的就是“确定下一阶段的状态”，还是回到上例，从阶段2的B1状态出发有三条路，也就是三个决策，分别导向阶段3的C1、C2、C3三个状态，即D2(B1)={C1,C2,C3}。
有了决策，我们可以定义状态转移：动态规划中本阶段的状态往往是上一阶段和上一阶段的决策结果，由第k段的状态sk和本阶段的决策uk确定第k+1段的状态sk+1的过程叫状态转移。状态转移规律的形式化表示sk+1=Tk(sk,uk)称为状态转移方程。
这样看来，似乎决策和状态转移有着某种联系。我的理解，状态转移是决策的目的，决策是状态转移的途径。
各段决策确定后，整个问题的决策序列就构成一个策略，用p1,n={u1(s1),u2(s2),…, un(sn)}表示。对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作P1,n，使整个问题达到最有效果的策略就是最优策略。[1]
说到这里，又可以提出运用动态规划的一个前提。即这个过程的最优策略应具有这样的性质：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略[1]。这就是最优化原理。简言之，就是“最优策略的子策略也是最优策略”。
§1.4最优化原理与无后效性
这里，我把最优化原理定位在“运用动态规划的前提”。这是因为，是否符合最优化原理是一个问题的本质特征。对于不满足最优化原理的一个多阶段决策问题，整体上的最优策略p1,n同任何一个阶段k上的决策uk或任何一组阶段k1…k2上的子策略pk1,k2都不存在任何关系。如果要对这样的问题动态规划的话，我们从一开始所作的划分阶段等努力都将是徒劳的。
而我把无后效性定位在“应用动态规划的条件”，是因为动态规划是按次序去求每阶段的解，如果一个问题有后效性，那么这样的次序便是不合理的。但是，我们可以通过重新划分阶段，重新选定状态，或者增加状态变量的个数等手段，来是问题满足无后效性这个条件。说到底，还是要确定一个“序”。
在信息学的多阶段决策问题中，绝大部分都是能够满足最优化原理的，但它们往往会在后效性这一点上来设置障碍。所以在解题过程中，我们会特别关心“序”。对于有序的问题，就会考虑到动态规划；对于无序的问题，也会想方设法来使其有序。
§1.5最优指标函数和规划方程
最优指标函数：用于衡量所选定策略优劣的数量指标称为指标函数，最优指标函数记为fk(sk)，它表示从第k段状态sk采用最优策略p*k,n到过程终止时的最佳效益值[1]。
最优指标函数其实就是我们真正关心的问题的解。在上面的例子中，f2(B1)就表示从B1点到终点D1点的最短路径长度。我们求解的最终目标就是f1(A1)。
最优指标函数的求法一般是一个从目标状态出发的递推公式，称为规划方程：

其中sk是第k段的某个状态，uk是从sk出发的允许决策集合Dk(sk)中的一个决策，Tk(sk,uk)是由sk和uk所导出的第k+1段的某个状态sk+1，g(x,uk)是定义在数值x和决策uk上的一个函数，而函数opt表示最优化，根据具体问题分别表为max或min。
，称为边界条件。
上例中的规划方程就是：

边界条件为
这里是一种从目标状态往回推的逆序求法，适用于目标状态确定的问题。在我们的信息学问题中，也有很多有着确定的初始状态。当然，对于初始状态确定的问题，我们也可以采用从初始状态出发往前推的顺序求法。事实上，这种方法对我们来说要更为直观、更易设计一些，从而更多地出现在我们的解题过程中。
我们本节所讨论的这些理论虽然不是本文的主旨，但是却对下面要说的动态规划的特点起着基础性的作用。
§2动态规划的设计与实现
上面我们讨论了动态规划的一些理论，本节我们将通过几个例子中，动态规划的设计与实现，来了解动态规划的一些特点。
§2.1动态规划的多样性
[例2] 花店橱窗布置问题（IOI99）试题见附录
本题虽然是本届IOI中较为简单的一题，但其中大有文章可作。说它简单，是因为它有序，因此我们一眼便可看出这题应该用动态规划来解决。但是，如何动态规划呢？如何划分阶段，又如何选择状态呢？
<方法1>以花束的数目来划分阶段。在这里，阶段变量k表示的就是要布置的花束数目（前k束花），状态变量sk表示第k束花所在的花瓶。而对于每一个状态sk，决策就是第k-1束花应该放在哪个花瓶，用uk表示。最优指标函数fk(sk)表示前k束花，其中第k束插在第sk个花瓶中，所能取得的最大美学值。
状态转移方程为
规划方程为
（其中A(i,j)是花束i插在花瓶j中的美学值）
边界条件 （V是花瓶总数，事实上这是一个虚拟的边界）
<方法2>以花瓶的数目来划分阶段。在这里阶段变量k表示的是要占用的花瓶数目（前k个花瓶），状态变量sk表示前k个花瓶中放了多少花。而对于任意一个状态sk，决策就是第sk束花是否放在第k个花瓶中，用变量uk=1或0来表示。最优指标函数fk(sk)表示前k个花瓶中插了sk束花，所能取得的最大美学值。
状态转移方程为
规划方程为
边界条件为
两种划分阶段的方法，引出了两种状态表示法，两种规划方式，但是却都成功地解决了问题。只不过因为决策的选择有多有少，所以算法的时间复杂度也就不同。[2]
这个例子具有很大的普遍性。有很多的多阶段决策问题都有着不止一种的阶段划分方法，因而往往就有不止一种的规划方法。有时各种方法所产生的效果是差不多的，但更多的时候，就像我们的例子一样，两种方法会在某个方面有些区别。
所以，在用动态规划解题的时候，可以多想一想是否有其它的解法。对于不同的解法，要注意比较，好的算法好在哪里，差一点的算法差在哪里。从各种不同算法的比较中，我们可以更深刻地领会动态规划的构思技巧。
§2.2动态规划的模式性
这个可能做过动态规划的人都有体会，从我们上面对动态规划的分析也可以看出来。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的，否则问题就无法求解。
选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。
写出规划方程（包括边界条件）：在第一部分中，我们已经给出了规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。
动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。大体上的框架如下：
对f1(s1)初始化（边界条件）
for kß2 to n（这里以顺序求解为例）
对每一个skÎSk
fk(sk)ß一个极值（∞或－∞）
对每一个uk(sk)ÎDk(sk)
sk-1ßTk(sk,uk)
tßg(fk-1(sk-1),uk)
y t比fk(sk)更优 n
fk(sk)ßt
输出fn(sn)
这个N-S图虽然不能代表全部，但足可以概括大多数。少数的一些特殊的动态规划，其实现的原理也是类似，可以类比出来。我们到现在对动态规划的分析，主要是在理论上、设计上，原因也就在此。
掌握了动态规划的模式性，我们在用动态规划解题时就可以把主要的精力放在理论上的设计。一旦设计成熟，问题也就基本上解决了。而且在设计算法时也可以按部就班地来。
但是“物极必反”，太过拘泥于模式就会限制我们的思维，扼杀优良算法思想的产生。我们在解题时，不妨发挥一下创造性，去突破动态规划的实现模式，这样往往会收到意想不到的效果。[3]
§2.3动态规划的技巧性
上面我们所说的动态规划的模式性，主要指的是实现方面。而在设计方面，虽然它较为严格的步骤性，但是它的设计思想却是没有一定的规律可循的。这就需要我们不断地在实践当中去掌握动态规划的技巧，下面仅就一个例子谈一点我自己的体会。
[例3] 街道问题：在下图中找出从左下角到右上角的最短路径，每步只能向右方或上方走。
这是一道简单而又典型的动态规划题，许多介绍动态规划的书与文章中都拿它来做例子。通常，书上的解答是这样的：

按照图中的虚线来划分阶段，即阶段变量k表示走过的步数，而状态变量sk表示当前处于这一阶段上的哪一点（各点所对应的阶段和状态已经用ks在地图上标明）。这时的模型实际上已经转化成了一个特殊的多段图。用决策变量uk=0表示向右走，uk=1表示向上走，则状态转移方程如下：

（这里的row是地图竖直方向的行数）
我们看到，这个状态转移方程需要根据k的取值分两种情况讨论，显得非常麻烦。相应的，把它代入规划方程而付诸实现时，算法也很繁。因而我们在实现时，一般是不会这么做的，而代之以下面方法：
将地图中的点规则地编号如上，得到的规划方程如下：

（这里Distance表示相邻两点间的边长）
这样做确实要比上面的方法简单多了，但是它已经破坏了动态规划的本来面目，而不存在明确的阶段特征了。如果说这种方法是以地图中的行（A、B、C、D）来划分阶段的话，那么它的“状态转移”就不全是在两个阶段之间进行的了。
也许这没什么大不了的，因为实践比理论更有说服力。但是，如果我们把题目扩展一下：在地图中找出从左下角到右上角的两条路径，两条路径中的任何一条边都不能重叠，并且要求两条路径的总长度最短。这时，再用这种“简单”的方法就不太好办了。
如果非得套用这种方法的话，则最优指标函数就需要有四维的下标，并且难以处理两条路径“不能重叠”的问题。
而我们回到原先“标准”的动态规划法，就会发现这个问题很好解决，只需要加一维状态变量就成了。即用sk=(ak,bk)分别表示两条路径走到阶段k时所处的位置，相应的，决策变量也增加一维，用uk=(xk,yk)分别表示两条路径的行走方向。状态转移时将两条路径分别考虑：

在写规划方程时，只要对两条路径走到同一个点的情况稍微处理一下，减少可选的决策个数：

从这个例子中可以总结出设计动态规划算法的一个技巧：状态转移一般是在相邻的两个阶段之间（有时也可以在不相邻的两个阶段间），但是尽量不要在同一个阶段内进行。
动态规划是一种很灵活的解题方法，在动态规划算法的设计中，类似的技巧还有很多。要掌握动态规划的技巧，有两条途径：一是要深刻理解动态规划的本质，这也是我们为什么一开始就探讨它的本质的原因；二是要多实践，不但要多解题，还要学会从解题中探寻规律，总结技巧。
§3动态规划与一些算法的比较
动态规划作为诸多解题方法中的一种，必然和其他一些算法有着诸多联系。从这些联系中，我们也可以看出动态规划的一些特点。
§3.1动态规划与递推
——动态规划是最优化算法
由于动态规划的“名气”如此之大，以至于很多人甚至一些资料书上都往往把一种与动态规划十分相似的算法，当作是动态规划。这种算法就是递推。实际上，这两种算法还是很容易区分的。
按解题的目标来分，信息学试题主要分四类：判定性问题、构造性问题、计数问题和最优化问题。我们在竞赛中碰到的大多是最优化问题，而动态规划正是解决最优化问题的有力武器，因此动态规划在竞赛中的地位日益提高。而递推法在处理判定性问题和计数问题方面也是一把利器。下面分别就两个例子，谈一下递推法和动态规划在这两个方面的联系。
[例4] mod 4 最优路径问题：在下图中找出从第1点到第4点的一条路径，要求路径长度mod 4的余数最小。
这个图是一个多段图，而且是一个特殊的多段图。虽然这个图的形式比一般的多段图要简单，但是这个最优路径问题却不能用动态规划来做。因为一条从第1点到第4点的最优路径，在它走到第2点、第3点时，路径长度mod 4的余数不一定是最小，也就是说最优策略的子策略不一定最优——这个问题不满足最优化原理。
但是我们可以把它转换成判定性问题，用递推法来解决。判断从第1点到第k点的长度mod 4为sk的路径是否存在，用fk(sk)来表示，则递推公式如下：
（边界条件）

（这里lenk,i表示从第k-1点到第k点之间的第i条边的长度，方括号表示“或(or)”运算）
最后的结果就是可以使f4(s4)值为真的最小的s4值。
这个递推法的递推公式和动态规划的规划方程非常相似，我们在这里借用了动态规划的符号也就是为了更清楚地显示这一点。其实它们的思想也是非常相像的，可以说是递推法借用了动态规划的思想解决了动态规划不能解决的问题。
有的多阶段决策问题（像这一题的阶段特征就很明显），由于不能满足最优化原理等使用动态规划的先决条件，而无法应用动态规划。在这时可以将最优指标函数的值当作“状态”放到下标中去，从而变最优化问题为判定性问题，再借用动态规划的思想，用递推法来解决问题。
§3.2动态规划与搜索
——动态规划是高效率、高消费算法
同样是解决最优化问题，有的题目我们采用动态规划，而有的题目我们则需要用搜索。这其中有没有什么规则呢？
我们知道，撇开时空效率的因素不谈，在解决最优化问题的算法中，搜索可以说是“万能”的。所以动态规划可以解决的问题，搜索也一定可以解决。
把一个动态规划算法改写成搜索是非常方便的，状态转移方程、规划方程以及边界条件都可以直接“移植”，所不同的只是求解顺序。动态规划是自底向上的递推求解，而搜索则是自顶向下的递归求解（这里指深度搜索，宽度搜索类似）。
反过来，我们也可以把搜索算法改写成动态规划。状态空间搜索实际上是对隐式图中的点进行枚举，这种枚举是自顶向下的。如果把枚举的顺序反过来，变成自底向上，那么就成了动态规划。（当然这里有个条件，即隐式图中的点是可排序的，详见下一节。）
正因为动态规划和搜索有着求解顺序上的不同，这也造成了它们时间效率上的差别。在搜索中，往往会出现下面的情况：
对于上图(a)这样几个状态构成的一个隐式图，用搜索算法就会出现重复，如上图(b)所示，状态C2被搜索了两次。在深度搜索中，这样的重复会引起以C2为根整个的整个子搜索树的重复搜索；在宽度搜索中，虽然这样的重复可以立即被排除，但是其时间代价也是不小的。而动态规划就没有这个问题，如上图(c)所示。
一般说来，动态规划算法在时间效率上的优势是搜索无法比拟的。（当然对于某些题目，根本不会出现状态的重复，这样搜索和动态规划的速度就没有差别了。）而从理论上讲，任何拓扑有序（现实中这个条件常常可以满足）的隐式图中的搜索算法都可以改写成动态规划。但事实上，在很多情况下我们仍然不得不采用搜索算法。那么，动态规划算法在实现上还有什么障碍吗？
考虑上图(a)所示的隐式图，其中存在两个从初始状态无法达到的状态。在搜索算法中，这样的两个状态就不被考虑了，如上图(b)所示。但是动态规划由于是自底向上求解，所以就无法估计到这一点，因而遍历了全部的状态，如上图(c)所示。
一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的事搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。
如何协调好动态规划的高效率与高消费之间的矛盾呢？有一种折衷的办法就是记忆化算法。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。
§3.3动态规划与网络流
——动态规划是易设计易实现算法
由于图的关系复杂而无序，一般难以呈现阶段特征（除了特殊的图如多段图，或特殊的分段方法如Floyd），因此动态规划在图论中的应用不多。但有一类图，它的点却是有序的，这就是有向无环图。
在有向无环图中，我们可以对点进行拓扑排序，使其体现出有序的特征，从而据此划分阶段。在有向无还图中求最短路径的算法[4]，已经体现出了简单的动态规划思想。但动态规划在图论中还有更有价值的应用。下面先看一个例子。
[例6] N个人的街道问题：在街道问题（参见例3）中，若有N个人要从左下角走向右上角，要求他们走过的边的总长度最大。当然，这里每个人也只能向右或向上走。下面是一个样例，左图是从出发地到目的地的三条路径，右图是他们所走过的边，这些边的总长度为5 + 4 + 3 + 6 + 3 + 3 + 5 + 8 + 8 + 7 + 4 + 5 + 9 + 5 + 3 = 78（不一定是最大）。
这个题目是对街道问题的又一次扩展。仿照街道问题的解题方法，我们仍然可以用动态规划来解决本题。不过这一次是N个人同时走，状态变量也就需要用N维来表示，。相应的，决策变量也要变成N维，uk=(uk,1,uk,2,…,uk,N)。状态转移方程不需要做什么改动：

在写规划方程时，需要注意在第k阶段，N条路径所走过的边的总长度的计算，在这里我就用gk(sk,uk)来表示了：

边界条件为
可见将原来的动态规划算法移植到这个问题上来，在理论上还是完全可行的。但是，现在的这个动态规划算法的时空复杂度已经是关于N的指数函数，只要N稍微大一点，这个算法就不可能实现了。
下面我们换一个思路，将N条路径看成是网络中一个流量为N的流，这样求解的目标就是使这个流的费用最大。但是本题又不同于一般的费用流问题，在每一条边e上的流费用并不是流量和边权的乘积 ，而是用下式计算：

为了使经典的费用流算法适用于本题，我们需要将模型稍微转化一下：
如图，将每条边拆成两条。拆开后一条边上有权，但是容量限制为1；另一条边没有容量限制，但是流过这条边就不能计算费用了。这样我们就把问题转化成了一个标准的最大费用固定流问题。
这个算法可以套用经典的最小费用最大流算法，在此就不细说了。（参见附录中的源程序）
这个例题是我仿照IOI97的“障碍物探测器”一题[6]编出来的。“障碍物探测器”比这一题要复杂一些，但是基本思想是相似的。类似的题目还有99年冬令营的“迷宫改造”[7]。从这些题目中都可以看到动态规划和网络流的联系。
推广到一般情况，任何有向无环图中的费用流问题在理论上说，都可以用动态规划来解决。对于流量为N（如果流量不固定，这个N需要事先求出来）的费用流问题，用N维的变量sk=(sk,1,sk,2,…,sk,N)来描述状态，其中sk,iÎV(1£i£N)。相应的，决策也用N维的变量uk=(uk,1,uk,2,…,uk,N)来表示，其中uk,iÎE(sk,i)(1£i£N)，E(v)表示指向v的弧集。则状态转移方程可以这样表示：
sk-1,i = uk,i的弧尾结点
规划方程为
边界条件为
但是，由于动态规划算法是指数级算法，因而在实现中的局限性很大，仅可用于一些N非常小的题目。然而在竞赛解题中，比如上面说到的IOI97以及99冬令营测试时，我们使用动态规划的倾向性很明显（“障碍物探测器”中，我们用的是贪心策略，求N=1或N=2时的局部最优解[8]）。这主要有两个原因：
一． 虽然网络流有着经典的算法，但是在竞赛中不可能出现经典的问题。如果要运用网络流算法，则需要经过一番模型转化，有时这个转化还是相当困难的。因此在算法的设计上，灵活巧妙的动态规划算法反而要更为简单一些。
二． 网络流算法实现起来很繁，这是被人们公认的。因而在竞赛的紧张环境中，实现起来有一定模式的动态规划算法又多了一层优势。
正由于动态规划算法在设计和实现上的简便性，所以在N不太大时，也就是在动态规划可行的情况下，我们还是应该尽量运用动态规划。
§4结语
本文的内容比较杂，是我几年来对动态规划的参悟理解、心得体会。虽然主要的篇幅讲的都是理论，但是根本的目的还是指导实践。
动态规划，据我认为，是当今信息学竞赛中最灵活、也最能体现解题者水平的一类解题方法。本文内容虽多，不能涵盖动态规划之万一。“纸上得来终觉浅，绝知此事要躬行。”要想真正领悟、理解动态规划的思想，掌握动态规划的解题技巧，还需要在实践中不断地挖掘、探索。实践得多了，也就能体会到渐入佳境之妙了。