【正文】 S） ................................................................................ 54 （ Cross Product） .................................................................................................................... 54 （ Determining Intersections） ................................................................................ 55 三、點集的性質(zhì) （ POINTSET PROPERITIES） ....................................................................................... 57 （ Finding the convex hull） ............................................................................................. 57 第四章 動態(tài)規(guī)劃 ........................................................................................................................................ 63 一、引言 —— 由一個問題引出的算法 ................................................................................................. 63 二、動態(tài)規(guī)劃的基本概念 ...................................................................................................................... 65 動態(tài)規(guī)劃的發(fā)展及研究內(nèi)容 ........................................................................................................ 65 多階段決策問題 ............................................................................................................................. 65 決策過程的分類 ............................................................................................................................. 66 三、動態(tài)規(guī)劃模型的基本要素 .............................................................................................................. 66 四、動態(tài)規(guī)劃的基本定理和基本方程 ................................................................................................. 68 五、動態(tài)規(guī)劃的適用條件 ...................................................................................................................... 69 最優(yōu)化原理（最優(yōu)子結構性質(zhì)） ................................................................................................ 69 無后向性 ......................................................................................................................................... 70 子問題的重疊性 ............................................................................................................................. 70 六、動態(tài)規(guī)劃的基本思想 ...................................................................................................................... 71 七、動態(tài)規(guī)劃算法的基本步驟 .............................................................................................................. 72 八、 動態(tài)規(guī)劃的實例分析 ...................................................................................................................... 73 iv 例 1 生產(chǎn)計劃問題 .............................................................................................................................. 73 例 2 Bitonic 旅行路線問題 .................................................................................................................. 74 例 3 計算矩陣連乘積 ........................................................................................................................... 75 第五章 組合數(shù)學簡介 ............................................................................................................................... 80 一、概述 ................................................................................................................................................... 80 二、解組合數(shù)學題目的一些方法 .......................................................................................................... 81 三、 P211。 本次修訂版有 阮政、王洪剛和陳昊參與修訂，重寫了STL 和組合數(shù)學部分，并增加了算法優(yōu)化專題。 本書是由徐本柱主持，其中 初始 由 李曉泉 、 萬郁香 、 許嵩罡 、 周晉 、 龐博 、 曹力 和沈揚參與編寫的， 李曉泉 寫了 圖論及搜索 部分， 萬郁香 寫了 模擬類 部分， 許嵩罡 寫了 畫法幾何 部分， 周晉 寫了 密碼 部分，龐博 寫了 字符串處理 部分， 曹力 寫了 組合數(shù)學 部分， STL 簡介部分有許松罡和沈揚合寫。 計算機科學與技術系 修訂版 ICPC培訓講義 算法與程序設計 I C P C 培訓講義 算法與程序設計 ? 計算機科學與技術系 合肥工業(yè)大學 2020 年 3 月 修訂版 ii 前 言 ACM／ ICPC 是由國際計算機學界著名的 ACM 學會主辦，世界上公認的規(guī)模最大、水平最高的國際大學生程序設計競賽，它充分地展示了大學生分析問題和解決問題的能力，這項比賽，歷來為國際知名大學所重視，競賽分區(qū)域預賽和國際決賽兩個階段進行，各賽區(qū)預賽的第一名獲參加決賽的資格 （ 第二名 視情況而定） 。 中國的上海賽區(qū)于 1995 年度試舉辦，我校未參賽 ，從 1996 年正式舉辦起，我校每年都參加，并多次取得了較好的成績，為了更好的組織今后的比賽，我們于 2020 年開始著手編寫了這本講義，并希望作為資料保存下去，每年都得以增加更多更新的內(nèi)容?，F(xiàn)在大家使用的 后由 許嵩罡 負責整理并增加了動態(tài)規(guī)劃部分。 全書由徐本柱審校，由于時間匆忙，加上作者水平有限，錯誤難免，希望廣大同學批評指正。LYA 原理及其應用 ...................................................................................................................... 86 第六章 專題解析 ........................................................................................................................................ 93 一、模 擬 ................................................................................................................................................ 93 1. 模擬游戲類 ...................................................................................................................................... 93 2. 模擬編碼類 ...................................................................................................................................... 97 二、 密 碼 ........................................................................................................................................... 102 1. Problem A ........................................................................................................................................ 102 2. Problem B ........................................................................................................................................ 106 3. Problem C ........................................................................................................................................ 109 三、字符串處理 ..................................................................................................................................... 113 1. PROBLEM A.................................................................................................................................... 113 2. PROBLEM