[1]POJ 动态规划题目列表
容易：
1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵，求平衡）, 1936,1952, 1953, 1958, 1959, 1962, 1975, 1989, 2018, 2029,2039, 2063, 2081, 2082,2181, 2184, 2192, 2231, 2279, 2329, 2336, 2346, 2353,2355, 2356, 2385, 2392, 2424,
不易：
1019,1037, 1080, 1112, 1141, 1170, 1192, 1239, 1655, 1695, 1707,1733(区间减法加并查集), 1737, 1837, 1850, 1920(加强版汉罗塔), 1934(全部最长公共子序列), 1937(计算几何), 1964(最大矩形面积，O(n)算法), 2138, 2151, 2161(烦，没写), 2178,
推荐：
1015, 1635, 1636(挺好的), 1671, 1682, 1692(优化), 1704, 1717, 1722, 1726, 1732, 1770, 1821, 1853, 1949, 2019, 2127, 2176, 2228, 2287, 2342, 2374, 2378, 2384, 2411
状态DP
树DP
构造最优解
四边形不等式
单调队列
1015 Jury Compromise
1029 False coin
1036 Gangsters
1037 A decorative fence
1038 Bugs Integrated, Inc.
1042 Gone Fishing
1050 To the Max
1062 昂贵的聘礼
1074 Parallel Expectations
1080 Human Gene Functions
1088 滑雪
1093 Formatting Text
1112 Team Them Up!
1141 Brackets Sequence
1143 Number Game
1157 LITTLE SHOP OF FLOWERS
1159 Palindrome
1160 Post Office
1163 The Triangle
1170 Shopping Offers
1178 Camelot
1179 Polygon
1180 Batch Scheduling
1185 炮兵阵地
1187 陨石的秘密
1189 钉子和小球
1191 棋盘分割
1192 最优连通子集
1208 The Blocks Problem
1239 Increasing Sequences
1240 Pre-Post-erous!
1276 Cash Machine
1293 Duty Free Shop
1322 Chocolate
1323 Game Prediction
1338 Ugly Numbers
1390 Blocks
1414 Life Line
1432 Decoding Morse Sequences 1456 Supermarket
1458 Common Subsequence
1475 Pushing Boxes
1485 Fast Food
1505 Copying Books
1513 Scheduling Lectures
1579 Function Run Fun
1609 Tiling Up Blocks
1631 Bridging signals 2分+DP NLOGN 1633 Gladiators
1635 Subway tree systems
1636 Prison rearrangement
1644 To Bet or Not To Bet
1649 Market Place
1651 Multiplication Puzzle
1655 Balancing Act
1661 Help Jimmy
1664 放苹果
1671 Rhyme Schemes
1682 Clans on the Three Gorges 1690 (Your)((Term)((Project)))
1691 Painting A Board
1692 Crossed Matchings 1695 Magazine Delivery 1699 Best Sequence
1704 Georgia and Bob
1707 Sum of powers
1712 Flying Stars
1714 The Cave
1717 Dominoes
1718 River Crossing
1722 SUBTRACT
1726 Tango Tango Insurrection 1732 Phone numbers
1733 Parity game
1737 Connected Graph
1740 A New Stone Game 1742 Coins P
1745 Divisibility
1770 Special Experiment 1771 Elevator Stopping Plan 1776 Task Sequences
1821 Fence
1837 Balance
1848 Tree
1850 Code
1853 Cat
1874 Trade on Verweggistan 1887 Testing the CATCHER 1889 Package Pricing
1920 Towers of Hanoi
1926 Pollution
1934 Trip
1936 All in All
1937 Balanced Food
1946 Cow Cycling
1947 Rebuilding Roads
1949 Chores
1952 BUY LOW, BUY LOWER 1953 World Cup Noise
1958 Strange Towers of Hanoi 1959 Darts
1962 Corporative Network 1964 City Game
1975 Median Weight Bead 1989 The Cow Lineup
2018 Best Cow Fences
2019 Cornfields
2029 Get Many Persimmon Trees
2033 Alphacode
2039 To and Fro
2047 Concert Hall Scheduling
2063 Investment
2081 Recaman's Sequence
2082 Terrible Sets
2084 Game of Connections
2127 Greatest Common Increasing Subsequence 2138 Travel Games
2151 Check the difficulty of problems
2152 Fire
2161 Chandelier
2176 Folding
2178 Heroes Of Might And Magic
2181 Jumping Cows
2184 Cow Exhibition
2192 Zipper
2193 Lenny's Lucky Lotto Lists
2228 Naptime
2231 Moo Volume
2279 Mr. Young's Picture Permutations
2287 TianJi -- The Horse Racing
2288 Islands and Bridges
2292 Optimal Keypad
2329 Nearest number - 2
2336 Ferry Loading II
2342 Anniversary party
2346 Lucky tickets
2353 Ministry
2355 Railway tickets
2356 Find a multiple
2374 Fence Obstacle Course
2378 Tree Cutting
2384 Harder Sokoban Problem
2385 Apple Catching
2386 Lake Counting
2392 Space Elevator
2397 Spiderman
2411 Mondriaan's Dream
2414 Phylogenetic Trees Inherited
2424 Flo's Restaurant
2430 Lazy Cows
2915 Zuma
3017 Cut the Sequence
3028 Shoot-out
3124 The Bookcase
3133 Manhattan Wiring
3345 Bribing FIPA
3375 Network Connection
3420 Quad Tiling ?https://www.doczj.com/doc/9f9767695.html,/?cat=5
[2]动态规划方法总结
1. 按状态类型分
写在前面：
从状态类型分，并不表示一题只从属于一类。其实一类只是一种状态的表示方法。可以好几种方法组合成一个状态，来解决问题。
1.1. 编号（长度）动态规划
共性总结：
本类的状态是基础的基础，大部分的动态规划都要用到它，成为一个维。一般来说，有两种编号的状态：
1、状态(i)表示前i个元素决策组成的一个状态。
2、状态(i)表示用到了第i个元素，和其他在1到i-1间的元素，决策组成有的一个状态。
题库：
a) 最长不下降子序列
以一元组(i)作为状态，表示第i个作为序列的最后一个点的时候的最长序列。于是很容易想到O(n2)得算法。但本题可合理组织状态，引入一个单调的辅助数组，利用单调性二分查找，优化到O(nlogn)。关于优化详见优化章。
一些问题可将数据有序化，转化成本题。
应用：
拦截导弹(NOIP99 Advance 1) 就是原题。
Beautiful People (sgu199)，要将数据有序化：其中一个权作为第一关键字不下降排列，另一个权作为第二关键字不上升。
Segment (ural 107，将线段的左端点有序化就可以了。
b) LCS
状态(i,j)，表示第1个字符串的第i位，与第2个字符串的第j位匹配，得到的最长的串。若有多个串要LCS，则加维，即几个串就几个维。我也将此题归入路径问题。
c) 花店橱窗布置(IOI99)
见路径问题。
1.2. 区间动态规划
共性总结：
本类问题与下一章的划分问题的决策的分割点无序交集比较大（占本类问题的30%）。
题库：
a) 石子合并
见划分问题
b) 模版匹配(CEOI01,Patten)
这题特殊的地方是状态的值是一个集合而不是一个数。
c) 不可分解的编码(ACM World Final 2002)
d) Electric Path(ural1143)
e) 邮局(IOI2000 Day2 1)
若状态表示的思路从第i个村庄可以从属于哪个邮局，无最优子结构。转变一个方向：第k 个邮局可以“控制”一个区间的村庄[i,j]。于是方程就显然了:
f(k,i,j)=min{f(k-1,p,i-1)+w(i,j)}(k-1<=p<=i-1)
S(i) 为村庄i到原点的距离。
w(i,j)=min{k| Sum{|S(k)-S(p)|}(i<=p<=j)}(i<=k<=j) 找到[i,j]间最好的一个邮局点。不过可以发现Sum{|S(k)-S(p)|是单调的，所以取中位数就可以了。即上式中k的取值范围只有floor((i+j)/2), ceil((i+j)/2)两个。Floor是下取整。Ceil是上取整。这样每次转移时间降到O(1)。注意到是区间连续的，即(p,i-1) 和(i, j) 中的i-1, i是连续的，所以空间可以降维：f(i,j)表示放前i个邮局到前j个村庄的最优值。
f(i,j)=min{f(i-1,p-1)+w(p,j)}(i-1<=p<=j-1}
e(i,j) 为当f(i,j)到达最优值时的p.
通过证明四边形不等式，得到e(i,j)<=e(i,j+1)<=e(i+1,j+1)
决策数量又少了一个数量级。
1.3. 坐标动态规划
共性总结：
之后的一些问题，状态是由坐标维与其他的维组成。本类与划分问题(是2维或多维的坐标系的划分)与路径问题的交集占本类问题中大多数。
题库：
a) 棋盘分割(NOI99 4)
主要是将公式变形，变形后的公式很容易看出方程。状态是由2个坐标组成的4元组
(x1,y1)(x2,y2)，表示一个子棋盘。这有点像之前的区间动态规划，只不过是将1维转2维。后见路径问题。
1.4. 数轴动态规划
共性总结：
题库：
a) 01背包
应用：
装箱问题（NOIP01 Trade 4）
就是原题。
值币分割
可利用方程的性质，空间降1维。币值可重复的值币分割(pku1742, Problem F LouTianCheng’s Contest in POJ).使用左右法在定位上加速。另给状态加一个属性last,记录上一次剩下的可用的同币值硬币数（利用了当前转移是唯一前驱的特点）。
b) 取火柴问题(sgu153 Playing with matches)
c) Stone Pile(ural1005 Stone Pile)
d) 公路巡逻(CTSC2000)
1.5. 5.树型动态规划
共性总结：
1）动态规划的顺序
一般按照后序遍历的顺序，即处理完儿子再处理当前节点，才符合树的子结构的性质。
2）多叉树转换为二叉树
由于要分配附加维到各个节点，而分配附加维是个划分问题，若还是按当前节点到各个儿子节点分配，则成了一个整数划分问题,O(n2)。所以要把多叉树转换为二叉树，这样才能按动态规划的方式只决策当前点的分配问题, O(n)。
3）加当前点的选或不选的常数维
加此维解决的是后效性问题。
4）在将边信息转成树时的技巧
将读入的边分裂成2条边，将这2条边关联起来（就是找到一条边，另一条边的编号就知道）。用前向星表示法表示边（按起点有序），以后用边的时候，用了一条边打不可用标志，也将关联边打不可用标志。这样可以保证O(n)的时间完成信息处理，而且在父节点找儿子的过程中带来很大的方便。
5）复杂度
树型动态规划复杂度基本上是O(n)；若有附加维m，则是O(nm)。
题库：
a) 选课(CTSC97-3)
由于要分配课程数，所以要多叉树转换为二叉树。
b) 贪吃的九头龙(NOI02-3)
若小头数大于1的话，则让不同的小头吃一段树枝的2个端点。这样就把问题转化成：附加维是大头吃的个数，当前点由不由大头吃的常数维的动态规划。由于涉及划分问题，所以要多叉树转换为二叉树。
c) 求树的质心(sgu134 Centroid)
给出一棵边不带权的树，求点,使得去掉此点后,剩下的最大的连通子图的顶点数最小.
d) 求树中的点最远距离最近。
给出一棵边带权的树，求树中的点，使得此点到树中的其他结点的最远距离最近。
Computer Network (sgu149)
Computer Net (ural1056)
1.6. 集合动态规划（状态压缩）
共性总结：
1) 数据特殊性
给出的数据在某一个或几个维度上一般具有比较小的范围（可以枚举一类的状态）。一个枚举的状态是一个集合。
2) 编码
由于集合中元素个数的不定性或范围大，直接开数组存，不好索引数组（编程复杂度太高），所以要将集合编码。利用数据的可枚举性，将枚举的状态(集合)编码。一般来说码值的范围要很小（尽量排除无用的码值，如炮兵：当前格和上格存在炮兵的情况是非法的，可以排除）。规定编码的码值代表的意思，要尽量规定好维护的码值。（如炮兵：当前格存在炮兵的用2，上格存在炮兵用1。这样下一层的规划时，只要码值-1即可）。有时候可以直接利用编码的顺序动态规划，因为这时编码已经是拓补有序。如TSP问题当前已选点集合的状态的前驱的编码的值一定比当前的编码的值小。
3) 状态压缩
对有限阶段的放置情况，行走情况编码（其实质也是放置的集合或行走路线的集合），这样的编码，也有人谓之：“状态压缩”。此类题以“炮兵阵地”为典型，进行扩展。
题库
a) 购物（IOI95-2）
可将每种物品按5进制编码。（5为每种物品数的上限）由于物品数的上限为5，比较小，也可直接开数组存。
b) Roger游戏任务一（CTSC98 Day2 4）
一个正方体在一个方格内的状态只有24种，而且可以通过顶面和前面来表示，这样用3维的状态(x,y,p)就可以解决，p为1到24种状态中的一种。
c) TSP问题
观察一下TSP的搜索过程：for (x in 未选点) TSP(x)
即当前路的最后一个节点为x,现在要选择下一个节点y,而y要在未选点的集合中。若未选点或已选点的集合已确定，则后效性消除。可以DP。状态为令X为当前路的已选点的集合(含i)，当前路的最后一个节点为i。2元组(X,i)为经过已选点的集合X到节点i的最短长度。将X 编码即可。
注意：并没有因为动态规划将问题从NP类带到P类。
应用: DNA Laboratory(Problem B,TU-Darmstadt Programming Contest 2004)
将每个串的交迭部分求出，就可以将问题专成TSP，但要输出字典序最小的，则需要注意DP顺序。有具体的报告。
d) 炮兵阵地
十分经典，详见报告。
应用:
Another Chocolate Maniac(sgu132) 类似炮兵的做法的最值，只不过是求最小值，麻烦点。Hardwood floor(sgu131) 类似炮兵的做法的统计
Little Knights(sgu225) 类似炮兵的做法的统计,数据量太大要const
Little Kings(sgu223) 类似炮兵的做法的统计
Bugs公司(CEOI 2002) 类似炮兵的做法的最值
1.7. 利用动态规划思想求最值，编号（循环变量）的迭代
共性总结：
要利用上次的一些运算“剩下”的循环变量作当前循环的边界，主要在于找出一种决策顺序，使之成立。
题库：
a) 奶牛浴场
b) Communication System
将数据有序化, 从大到小枚举带宽, 每次可利用上次处理的结果Min, 来决策当前状态。称作迭代, 或就是一种动态规划。
(zju1409, Problem C Tehran 2002 Iran Nationwide Internet Programming Contest)
1.8. 记忆化搜索题库
a) Magic Trick (Problem G, TU-Darmstadt Programming Contest 2004)
2. 按转移方式分
2.1. 存在性
递推
1)01统计(CTSC99 1)
2)卡特兰数
circle(sgu130)
3)鹰蛋
2.2. 求一系列的分割（合并）点（划分问题）
2.2.1. 决策的分割点有序
共性总结：
a) 有序性
每次决策的点的编号是有序的，即要按决策的顺序输出分割点的编号的话，编号是有序的，满足分割点的编号按升序排列。
b) 方程一般形式
f(n,m)=optimize{f(k,m-1)+w(k+1,n)}
(n,m)表示从1到n个点中划分为m个部分的最优值；k为决策的分割点，即第m个部分为k+1到n；这里optimize可以为max,min。
题库：
a) 整数划分
常应用在将一个权分配给一定的小分割块，如：将大堆的石子分成一定的小堆，小堆可为空，大堆要分完。有时应用在树型动态规划（二叉转多叉）中。
b) 乘积最大(NOIP00 Advance 2)
就是按上面的一般式的方程做。
2.2.2. 决策的分割点无序
共性总结：
a) 无序性
每次决策的点的编号是无序的，即要按决策的递归顺序输出分割点的编号的话，编号是无序的。
b) 方程一般形式
f(i,j)=optimize{f(i,k-1)+f(k+1,j)}+w(i,j)
(i,j)表示从i到j的范围内选取一个分割点k的最优值，子问题是分割点左边(i,k-1)和右边(k+1,j)的点的范围的最优值；这里optimize可以为max,min。方程很类似2叉树的性质。
c) 四边形不等式
此类的问题，有些可用四边形不等式优化。见优化章。
题库：
a) 石子合并(NOI95 2)
经典，详见报告。可用四边形不等式优化成O(n2)，其实还可以用类似堆的数据结构在O(nlogn)的时间内完成，但这就不是动态规划了。
应用：
a) 构造最优二叉排序树(CTSC96 2)
b) 多边形(IOI9
这题值的正负号处理要注意，乘法运算，由于符号的加入，使原本的正的最优解，一下变成负的。
c) 加分二叉树(NOIP03 Advance 3)
方程就是一般式，转移的函数：w(i,j)=sum(i,k-1)*sum(k+1,j)+d(k)。由于w(i,j)不满足凸单调性，所以不能用四边形不等式优化。
d) 括号序列(Problem B, NEERC 2001)
这题的分割点不是一个元素，而是元素间的一条线。主要的思维方式是从递归定义。
2.3. 路径问题
共性总结：
a) 行走方向决定阶段性
有规定源点与终点。每次行走方向都有一定的规定，使原点到终点的所有路径形成无环有向图。
b) 多源或多汇
当多源或多汇时，应该加维，使得每个源，都有一个路径的状态与之对应。如有n个源的网格类问题，常常转态是(x1,y1)(x2,y2)… (xn,yn)。但是源太多的话，空间上不允许，可以降问题转成网络流问题。
c) 双向动态规划
由于有规定源点与终点，可以双向动态规划，但要考虑效果好不好，理论上是比原来少1/2，但有时由于可用于决策的状态较少，效果就不错了。
d) 决策稀疏性
就是所谓走法，若对于一个状态，它的前驱或者后继数很少(从无环有向图角度，就是入度或出度少)，称决策稀疏。
e) 状态稀疏性
就是很多状态是没有用的，如排列的LCS,状态为2维的(x,y)，但对于一个x只有一个y是有效个。所以实质上状态数还是线形的。本类一些技巧性的东西较多，在题库中具体说明。
题库：
a) 方格取数(NOIP00 advance 4)
(x1,y1)(x2,y2)对角线空间优化
b) 花店橱窗布置(IOI99)
我对本题有个小改造：若花瓶无序，如何做，有序指：对于花束i<花束j, 花束i对应的花瓶编号<花束j对应的花瓶编号。那么这样就是一个NP问题了，可用后面的基于状态压缩的动态规划解决。
3. 动态规划的优化
3.1. 迭代
3.2. 四边形
3.3. 凸性的优化
[3]动态规划资料下载
https://www.doczj.com/doc/9f9767695.html,/download/2___12-7.ppt
主题公园主要有哪几种类型？ 是根据某个特定的主题，采用现代科学技术和多层次活动设置方式，集诸多娱乐活动、休闲要素和服务接待设施于一体的现代。其主要类型有： 一、按旅游体验类型分 1.游乐型。游乐型的主题公园亦称游乐园，提供了刺激的游乐设施和机动游戏，如迪士尼乐园、蒂沃利公园、发现王国等。 2.情景模拟型。情景模拟型，目前主要指各种影视城的，如三国水浒城、浙江横店影视基地、上海科技馆等。 3.观光型。观光型的主要是着名景观或特色景观的浓缩，让游客在短暂的时间欣赏最特色的景观，如锦绣中华、世界之窗等。 4. 主题型。主题型的主要是各式各样的水族馆和野生动物公园，如老虎滩极地海洋公园、香港海洋公园等。 5. 风情体验型。风情体验为题的，则将不同的民族风俗和民族色彩展现在游客眼前。 二、按功能和用途分 1.微缩景观类。这类主要是选择世界各地或全国各地有代表意义的景观进行微缩，如深圳锦绣中华、北京世界公园等。 2.影视。这类主题公园不以影视拍摄功能为主，而是成为以影视拍摄场景、场地、道具、服饰、片段等为资源，以影视文化为主题的娱乐公园，如好莱坞环球影城、无锡三国城、唐城、水浒城等。 3.活动参与类。以丰富的互动性、竞技性和娱乐性吸引了世界各地的游客，如AC米兰、苏州乐园、深圳华侨城、欢乐谷等。
4.民俗景观和仿古建筑类。如中华民俗文化村、北京民族园等。 5.科幻探险类。如江苏常州的中华恐龙园等。 三、按主题内容分 按主题内容分，主要有：以花卉园艺为主题，以保存文化、历史为主题，以异国地理环境，动植物特征为主题，以博览会、博物馆为主题，以童话幻想、科学、宇宙为主题等。
[1]POJ动态规划题目列表 容易： 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵，求平衡）, 1936,1952, 1953, 1958, 1959, 1962, 1975, 1989, 2018, 2029,2039, 2063, 2081, 2082,2181, 2184, 2192, 2231, 2279, 2329, 2336, 2346, 2353,2355, 2356, 2385, 2392, 2424, 不易： 1019,1037, 1080, 1112, 1141, 1170, 1192, 1239, 1655, 1695, 1707,1733(区间减法加并查集), 1737, 1837, 1850, 1920(加强版汉罗塔), 1934(全部最长公共子序列), 1937(计算几何), 1964(最大矩形面积，O(n)算法), 2138, 2151, 2161(烦，没写), 2178, 推荐： 1015, 1635, 1636(挺好的), 1671, 1682, 1692(优化), 1704, 1717, 1722, 1726, 1732, 1770, 1821, 1853, 1949, 2019, 2127, 2176, 2228, 2287, 2342, 2374, 2378, 2384, 2411 状态 DP 树 DP 构造最优解四边形不等式单调队列 1015 Jury Compromise 1029 False coin 1036 Gangsters 1037 A decorative fence 1038 Bugs Integrated, Inc. 1042 Gone Fishing 1050 To the Max 1062 昂贵的聘礼 1074 Parallel Expectations 1080 Human Gene Functions 1088 滑雪 1093 Formatting Text 1112 Team Them Up! 1141 Brackets Sequence 1143 Number Game
动态规划作业 1、1、设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目的地，其间的运输成本如图中所标的数字，试求运费最低的路线? 把A看作终点，该问题可分为4个阶段。 f k(S k)表示从第K阶段点S k到终点A的最短距离。 f4(B1)=20，f4(B2)=40，f4(B3)=30 f3(C1)=min[d3(C1,B1)+ f4(B1), d3(C1,B2)+ f4(B2), d3(C1,B3)+ f4(B3) ]=70，U3(C1)= B2 或B3 f3(C2)=40 ，U3(C2)= B3 f3(C3)=80 ，U3(C3)= B1或B2 或B3 f2(D1)=80 ，U2(D1)= C1 f2(D2)=70 ，U2(D2)= C2 f1(E)=110 ，U1(E)= D1或D2 所以可以得到以下最短路线，
E→D1→C1→B2 / B3→A E→D2→C2→B3→A 2、习题4－2 解：1)将问题按地区分为三个阶段，三个地区的编号分别为1、2、3； 2)设Sk表示为分配给第k个地区到第n个地区的销售点数， Xk表示为分配给第k个地区的销售点数，S k＋1＝S k－X k Pk(Xk)表示为Xk个销售点分到第k个地区所得的利润值 fk(Sk)表示为Sk个销售点分配给第k个地区到第n个地区的最大利润值 3)递推关系式： fk(Sk)＝max[ Pk(Xk)+ f k+1(S k－X k) ] k=3,2,1 f4(S4)＝0 4）从最后一个阶段开始向前逆推计算 第三阶段： 设将S3个销售点（S3＝0,1,2,3,4）全部分配给第三个地区时，最大利润值为： f3(S3)＝max[P3(X3)] 其中X3＝S3＝0,1,2,3,4 表1
状态压缩 Abstract 信息学发展势头迅猛，信息学奥赛的题目来源遍及各行各业，经常有一些在实际应用中很有价值的问题被引入信息学并得到有效解决。然而有一些问题却被认为很可能不存在有效的(多项式级的)算法，本文以对几个例题的剖析，简述状态压缩思想及其应用。 Keywords 状态压缩、Hash、动态规划、递推 Content Introducti o n 作为OIers，我们不同程度地知道各式各样的算法。这些算法有的以O(logn)的复杂度运行，如二分查找、欧几里德GCD算法(连续两次迭代后的余数至多为 原数的一半)、平衡树，有的以)运行，例如二级索引、块状链表，再往上有O(n)、O(n p log q n)……大部分问题的算法都有一个多项式级别的时间复杂度上界1，我们一般称这类问题2为P (deterministic Polynomial-time)类问题，例如在有向图中求最短路径。然而存在几类问题，至今仍未被很好地解决，人们怀疑他们根本没有多项式时间复杂度的算法，NPC(NP-Complete)和NPH(NP-Hard)就是其中的两类，例如问一个图是否存在哈密顿圈(NPC)、问一个图是否不存在哈密顿圈(NPH)、求一个完全图中最短的哈密顿圈(即经典的Traveling Salesman Problem货郎担问题，NPH)、在有向图中求最长(简单)路径(NPH)，对这些问题尚不知有多项式时间的算法存在。P和NPC都是NP(Non-deterministic Polynomial-time)的子集，NPC则代表了NP类中最难的一类问题，所有的NP类问题都可以在多项式时间内归约到NPC问题中去。NPH包含了NPC和其他一些不属于NP(也更难)的问题，NPC问题的函数版本(相对于判定性版本)一般是NPH的，例如问一个图是否存在哈密顿圈是NPC的，但求最短的哈密顿圈则是NPH的，原因在于我们可以在多项式时间内验证一个回路是否真的是哈密顿回路，却无法在多项式时间内验证其是否是最短的，NP类要求能在多项式时间内验证问题的一个解是否真的是一个解，所以最优化TSP问题不是NP的，而是NPH的。存在判定性TSP问题，它要求判定给定的完全图是否存在权和小于某常数v的哈密顿圈，这个问题的解显然可以在多项式时间内验证，因此它是NP 1请注意，大O符号表示上界，即O(n)的算法可以被认为是O(n2)的，O(n p log q n)可以被认为是O(n p+1)的。2在更正式的定义中，下面提到的概念都只对判定性问题或问题的判定版本才存在(NPH除外)。Levin给出了一个适用于非判定问题的更一般的概念，但他的论文比Cook的晚发表2年。
控规 控规是指控制性详细规划。 《城市规划编制办法》 第四节详细规划 第四十一条控制性详细规划应当包括下列内容： （一）确定规划范围内不同性质用地的界线，确定各类用地内适建，不适建或者有条件地允许建设的建筑类型。 （二）确定各地块建筑高度、建筑密度、容积率、绿地率等控制指标；确定公共设施配套要求、交通出入口方位、停车泊位、建筑后退红线距离等要求。 （三）提出各地块的建筑体量、体型、色彩等城市设计指导原则； （四）根据交通需求分析，确定地块出入口位置、停车泊位、公共交通场站用地范围和站点位置、步行交通以及其它交通设施。规定各级道路的红线、断面、交叉口形式及渠化措施、控制点坐标和标高。 （五）根据规划建设容量，确定市政工程管线位置、管径和工程设施的用地界线，进行管线综合。确定地下空间开发利用具体要求。 （六）制定相应的土地使用与建筑管理规定。 第四十二条控制性详细规划确定的各地块的主要用途、建筑密度、建筑高度、容积率、绿地率、基础设施和公共服务设施配套规定应当作为强制性内容。 控规在城市建设中的作用： 直接影响城市形态的规划层面。城市道路的线型、地块性质的调整都会直接影响这一街区的形态。而往往通过技术手段或者是从技术层面上说的最佳方往往又是最容易被城市规划执法者改变，或者说是各种利益体相互博弈的过程中不得不让步。 立法上控规是城市人民政府审批，也就是说修改不要通过人大。规划局代表市政府履行职责，那么也就是说控规的修改只要通过规划局就可以。 控制性详细规划是以城市总全规划或分区规划为依据，确定建设地区的土地使用性质和使用强度的控制指标、道路和工程管线控制性位置以及空间环境控制的规划要求。 控制性详细规划的主要任务是：以城市总体规划或分区规划为依据，确定建设地区的土地使用性质和使用强度的控制指标、道路和工程管线控制性位置以及空间环境控制的规划要求。 一、控制性详细规划 (一)现状资料与分析 调查了解上层次规划对本地区的规划要求及其现状基础资料，分析研究现状存在的主要问题及影响未来发展的主要因素，并作出评价。须收集以下基础资料： 1、总体规划或分区规划及各类专项规划对本地区的规划要求，相邻地段已批准的规划资料。 2、土地利用现状，用地分类至小类。
动态规划作业完整 WEIHUA system office room 【WEIHUA 16H-WEIHUA WEIHUA8Q8-
动态规划作业 1、1、设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目的地，其间的运输成本如图中所标的数字，试求运费最低的路线? 把A看作终点，该问题可分为4个阶段。 f k(S k)表示从第K阶段点S k到终点A的最短距离。 f4(B1)=20，f4(B2)=40，f4(B3)=30 f3(C1)=min[d3(C1, B1)+ f4(B1), d3(C1, B2)+ f4(B2), d3(C1, B3)+ f4(B3) ]=70，U3(C1)= B2 或B3 f3(C2)=40 ，U3(C2)= B3 f3(C3)=80 ，U3(C3)= B1或B2 或B3 f2(D1)=80 ，U2(D1)= C1 f2(D2)=70 ，U2(D2)= C2 f1(E)=110 ，U1(E)= D1或D2 所以可以得到以下最短路线，
E→D1→C1→B2 / B3→A E→D2→C2→B3→A 2、习题4－2 解：1)将问题按地区分为三个阶段，三个地区的编号分别为1、2、3； 2)设Sk表示为分配给第k个地区到第n个地区的销售点数， Xk表示为分配给第k个地区的销售点数，S k＋1＝S k－X k Pk(Xk)表示为Xk个销售点分到第k个地区所得的利润值 fk(Sk)表示为Sk个销售点分配给第k个地区到第n个地区的最大利润值 3)递推关系式： fk(Sk)＝max[ Pk(Xk)+ f k+1(S k－X k) ] k=3,2,1 f4(S4)＝0 4）从最后一个阶段开始向前逆推计算 第三阶段： 设将S3个销售点（S3＝0,1,2,3,4）全部分配给第三个地区时，最大利润值为： f3(S3)＝max[P3(X3)] 其中X3＝S3＝0,1,2,3,4 表1
动态规划是对最优化问题的一种新的算法设计方法。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的没计法对不同的问题，有各具特色的表示方式。不存在一种万能的动态规划算法。但是可以通过对若干有代表性的问题的动态规划算法进行讨论，学会这一设计方法。 多阶段决策过程最优化问题 ——动态规划的基本模型 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策最优化问题。 【例题1】最短路径问题。图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少? 【分析】把从A到E的全过程分成四个阶段，用k表示阶段变量，第1阶段有一个初始状态A，两条可供选择的支路ABl、AB2；第2阶段有两个初始状态B1、 B2，B1有三条可供选择的支路，B2有两条可供选择的支路……。用dk(x k，x k+1)表示在第k阶段由初始状态x k到下阶段的初始状态x k+1的路径距离，Fk(x k)表示从第k阶段的x k到终点E的最短距离，利用倒推方法求解A到E的最短距离。具体计算过程如下： S1：K=4，有：F4(D1)=3，F4(D2)=4，F4(D3)=3 S2: K=3，有： F3(C1)=min{d3(C1,D1)+F4(D1),d3(C1,D2)+F4(d2)}=min{8,10}=8 F3(C2)=d3(C2,D1)+f4(D1)=5+3=8 F3(C3)=d3(C3,D3)+f4(D3)=8+3=11 F3(C4)=d3(C4,D3)+f4(D3)=3+3=6
居住区规划布局的六种形式 从城市空间的角度讲，居住区是城市空间的重要层次与节点，上通城市下达小区、组团直到住宅内外空间，各空间层次有不同尺度和形态。根据居住区规划布局的实态可概括以下主要形式，大力提昌节约、集约式布局： 一、片块式布局 住宅建筑在尺度、形体、朝向等方面具有较多相同的因素，并以日照间距为主要依据建立起来的紧密联系所构成的群体，它们不强调主次等级，成片成块，成组成团地布置，形成片块式布局形式。一些居住区常采取与体制结构的行政区划相一致的布局形式，按体制规模划分地块，各地块配以相应的公共设施，并遵循日照间距布置建筑，因而自然地形成片块式布局形式，如北京五路居居住区，规整地将基地划分了四个居住小区片块，分别在各地块内配以小区中心，四个小区又配置一个共同的居住区中心，形成“居住区—居住小区”二级体制结构的片块式布局。吉林市通潭大路居住区，则将基地细分出20个居住组团地块，每个组团用地2.5～5hm2，分别在每个组团配置相应的活动中心，20个居住组团共同的居住区中心沿干道布置，形成“居住区—居住组团”二级体制结构的片块式布局。上海曲阳新居住区，则按居住区—居住小区—居住组团”的体制结构划分用地分别设置各级中心，形
成三级体制结构的片块式布局。 二、轴线式布局 空间轴线或可见或不可见，可见者常为线性的道路、绿带、水体等构成，但不论轴线的虚实，都具有强烈的聚集性和导向性。一定的空间要素沿轴布置，或对称或均衡，形成具有节奏的空间序列，起着支配全局的作用。如上海三林苑小区，以一步行水街为中心构成“水”轴线布局形式。百米长形水池，配以不锈钢群鱼雕塑、小天使喷泉、天然巨石、植草砖、架空层、孤形长廊，并以大片草坪(7500m2)衬托，具有显明的欧陆风格。广州东辉广场居住区，为一“路”轴线式布局，其特点是面对纵横两条城市干道穿越基地的不利条件，因势利导运用轴线式布。局手法，将公共服务设施绕两干道交叉口布置，形成聚合强大的居住区中心，同时用纵贯南北的步行绿带——绿轴，将基地南北边界滨河绿地连成一气，绿带内布置小学、托幼等日常性公共设施，成为有生气的信息传递纽带，各组团与绿带相通。此外还设一环形道路连通南北，以疏解纵横干道交通对居住区的干扰与分割。如此，被两条城市干道分割的基地便组成了有机整体。广东中山翠享槟榔小区，则采用多轴线的平行和交叉布局，将绿化景观、建筑群体串连起来，丰富而有序，尤其使一个个亲切的院落小空间统合成整体，不求宏伟场景但求温馨和谐。北京大吉城小区，以小区西北角的康有为故居广场为起点的
城乡规划的种类:城镇体系规划,城市规划,镇规划,乡规划,村庄规划 制定和实施城乡规划时应遵守的原则; 1.遵循城乡统筹,先规划后建设的原则; 2.防止污染和其它公害的原则; 3.保护生态环境,历史文化遗产和地方民族特色的原则; 4.符合区域人口发展,国防建设,防灾减灾的原则; 5.合理布局,节约用地,集约发展的原则; 历史文化名城保护规划编制的原则; 1,全面分析,因地制宜的原则; 2.保护与建设相协调的原则; 3.突出保护重点的原则; 城市新区开发的原则:量力而行的原则;统一规划,统一组织的原则;方便宜行的原则. 新区的开发类型:新市区的开发建设;经济开发区的建设;卫星城镇的开发建设;新工矿区的开发建设。 城市旧区改建原则：加强维护，逐步改建的原则；旧区改建与城市产业结构调整和工业企业技术改造的原则；旧区 改建与保护历史文物，名胜古迹相结合的原则。 城市绿地分类：公园绿地；生产绿地;防护绿地；附属绿地，其他绿地。 城市绿化规划的原则：城市绿化规划必须纳入城市总体规划；从实际出发，合理确定城市绿化规划指标。 绿化指标：人均公园绿地面积，城市绿化覆盖率，城市绿地率。 创建园林城市的法规有：国家园林城市标准和园林城市申报和审批办法。 城市绿化建设标准：（1）指标管理（2）道路绿化（3）居住区绿化（4）单位绿化（5）苗圃建设（6）城市全民义 务植树（7）立体绿化。 城市绿地的管理责任分工：城市公共绿地，风景林地，防护绿地，行道树及干道绿化带的绿化，由城市人民政府城 市绿化行政主管部门管理；各单位管界内的防护绿地的绿化，由该单位按照国家有关规定管理；单位自建的公园和 单位附属绿地的绿化，由该单位管理；居住区绿地的绿化，由城市人民政府城市绿化行政主管部门根据实际情况确 定的单位管理；城市苗圃，草圃和花圃等，由经营单位管理。 古树名木保护管理的原则：专业养护部门保护管理和单位，个人保护管理相结合的原则。 古树名木保护管理措施： （1）建立古树名木的确认，备案和档案制度。 （2）设立古树名木价值说明和保护标志。 （3）制定养护管理方案，落实养护管理责任制 （4）实行建设工程对古树名木的避让，保护措施。新建，改建，扩建的建设工程影响古树名木的生长的， 建设单位必须提出避让和保护措施。 （5）严禁砍伐和擅自移植古树名木，严格特殊情况下的移植批准程序。 风景名胜区的划分：国家级风景名胜区；省级风景名胜区。 风景名胜区总体规划的内容： （1）风景名胜区的评价。包括景源调查，景源筛选与分类，景源评分与分级，评价结论四部分。 （2）生态资源保护措施，重大建设项目布局，开发利用强度。 （3）风景名胜区的功能结构和空间布局。根据功能分区，确定土地利用规划，进行风景游赏组织。 （4）禁止开发和限制开发的范围。我国在“十一五”规划中明确提出了优化开发，重点开发， 限制开发和禁止开发的概念。生态薄弱和自然保护区域分别只是限制开发和禁止开发。 （5）风景名胜区的游客容量。风景区游人容量应随规划期限的不同而有变化，对一定规划范围的游人容量， 应综合分析并满足该地区的生态允许标准，游览心理标准，功能技术标准等因素而确定。 （6）有关专项规划。包括保护培育规划，风景游赏规划，典型景观规划，游览设施规划，基础工程规划， 居民社会调控规划，经济发展引导规划，土地利用协调规划，分期发展规划。 风景资源评价：景源调查，景源筛选与分类，景源评分与分级，评价结论四部分。风景名胜区的分区：生态保护区， 自然景观保护区，史迹保护区，风景恢复区，风景游览区，发展控制区。风景名胜区的分级：特级一级二级三级 保护区。风景名胜区建设是服从于风景资源保护这一首要任务的。风景名胜区的建设所追求的首先是社会效益和环境 效益，同时又要考虑经济效益。 风景名胜区建设的管理:可行性论证，建设用地管理，严格控制建设项目；建设项目的 审批程序；设计施工管理。城乡规划是指人民政府为了实现一定时期内本地区的经济和社会发展目标，事先依法制定 的用以确定城乡的性质规模和发展方向，城乡土地的合理利用，城乡的空间布局和城乡设施的科学配置的综合部署和 统一规划。城市是指国家按行政建制设立的，以非农产业和非农人口集聚为主要特征的居民点。公园绿地是指向公众 开放，以游憩为主要功能，兼具生态美化，防灾等作用的绿地。古树是指树龄在一百年以上的树木。名木是指国内外 稀有的以及具有历史价值和纪念意义，重要科研价值的树木。风景名胜区是指具有观赏，文化或者科学价值，自然景观，人文景观比较集中，环境优美，可供人们游览或者进行科学，文化活动的区域。风景资源指能引起审美及欣赏活动，可作为风景游览对象和风景开发利用的事物与因素的总称。游人容量是指单位时间，一定规划单元内所能容纳的游人数
动态规划讲解大全 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。 基本模型 多阶段决策过程的最优化问题。 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图） 这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。 记忆化搜索 给你一个数字三角形, 形式如下: 1 2 3 4 5 6 7 8 9 10 找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大. 无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)} 对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么
. 职业生涯规划有哪几种类型？每种类型有什么内容？很多人都是在工作了一段时间后，才意识到职业生涯规划的重要性。其实在你还没有意识到的时候，你的不少决定与行为就已经对你的职业生涯产生了影响。下面为您带来职业生涯规划有哪几种类型的详细内容。 文理科分班时，高考填写入学志愿时，大学时代学业、社会活动的安排，你是听信于父母、朋友、老师，凭自己的兴趣，或者随心所欲? 选择工作时，你是挑热门的行业，薪资高的工作，还是只图轻松? 工作中，你是“做一天和尚撞一天钟”，还是在为自己的未来做准备? 在处理职业问题时，每个人采用的方法不尽相同。有学者将职业生涯规划类型分为三类：依赖型、直觉型、理性型。 A依赖型：依赖父母、朋友、老师，或遵从书本与社会舆论。 大部分中国学生从小只知道不断学习课本上的知识，在就业之前很少关注与职业有关的事情。加之学校、社会也缺乏相关的教育与资讯，导致很多人都不能正确处理可能影响到以后职业发展的问题：在很多地方的高中，都会认为读文科的人比较笨，于是文理分科时，不少人明明喜欢文科，屈从于社会舆论会选择理科。填写大学志愿，听从父母、老师的安排，尽挑当时最热门的专业。我在帮客户做职业方向定位服务时，都会询问他们选择大学专业的原因，最常见的回答就是“当初什么都不懂，父母帮我选的”，“觉得这个职业以后收入不错”，迄今为止没有一个人是根据自己的兴趣能力自主选择的。考研、留学也不知道为了什么，只是因为身边的大部分人都这么做。 工作后很多人也想过职业规划，可无从下手。父母、朋友、书本说的都有道理，该听谁的呢?该作何决定呢?面对众多不尽相同的意见，当事人自己反而没了主意。 想起了一则杜撰的短文：联合国向全球青少年征文“对其它国家缺乏粮食的主见”，结果美国人不知道什么叫“其它国家”，欧洲人不知道什么叫“缺乏”，非洲人不知道什么叫“粮食”，中国人不知道什么叫“主见”。 如果你不假思索地执行别人的建议，最终也要由你承担结果，毕竟只有你才可以对自己的职业生涯负责。 所以说，在参考别人意见的同时，我们要有自己的主见。我们要学会解决问题的思路方法，这比现成的答案更重要，正所谓“授人以鱼，不如授人以渔也。” B直觉型：凭自己的直觉、一时的喜好做出决定。 在我咨询的案例中，不少人都曾经在某一阶段凭喜好做出职业决定。譬如因为感情受挫辞职疗伤、沉浸爱河无心工作、工作不顺频繁跳槽、收入不高追随热门…… 这种类型的人职业生涯最容易出现的隐患就是职业生涯不连贯，在每一领域的积累都不多，很难晋升到中高层。 当然，如果你清心寡欲、随遇而安、知足常乐，无衣食之忧，不在乎职场成败，随心所欲也是不错的选择，否则还是多用点心思。 C理性型：综合考虑个人与职场等因素，分析利弊得失，做出并执行相应的计划。 排除少数运气好的人在内，大部分职场成功人士在规划自己的职业生涯时，都是非常理性的。他们会及时关注职业信息，充分了解自我，制定合适的目标，并为目标而不断努力。 三种类型各有利弊。依赖型最省时省力，但是将自己的命运托付给他人，终究是一件危险的事情;直觉型短期内会很满足，可是长期来看随机性太强，会存在较大风险;理性型考虑周全，但是会花费较多时间与精力。 如果你在意职场的得失，追求事业的成功，如果你想在职业生涯中少一点烦恼，多一点快乐，建议你还是多花点时间与精力，多作些思考，做个“理性型”的人。 .
动态规划练习题 [题1] 多米诺骨牌（DOMINO） 问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。现有一行排列在桌面上：顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。顶行和底行的差值是2。这个差值是两行点数之和的差的绝对值。每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。 现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。 输入格式： 文件的第一行是一个整数n（1〈=n〈=1000〉，表示有n个多米诺骨牌在桌面上排成一行。接下来共有n行，每行包含两个整数a、b（0〈=a、b〈=6，中间用空格分开〉。第I+1行的a、b分别表示第I个多米诺骨牌的上部与下部的点数（0表示空）。 输出格式： 只有一个整数在文件的第一行。这个整数表示翻动骨牌的最少次数，从而使得顶行和底行的差值最小。 [题2] Perform巡回演出 题目描述: Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出). 由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表. 输入: 输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点Flute市,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n-1行是从城市2到其他城市(1,3,4...n)的航班,如此下去. 每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d个非负整数表示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如"3 75 0 80"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI,然后循环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束. 输出: 对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,输出0. 样例输入: 样例输出：
动态规划 一·动态规划法的发展及其研究内容 动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.BELLMAN等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段问题转化为一系列的单阶段问题，逐个求解创立了解决这类过程优化问题的新方法——动态规划。1957年出版的他的名著《Dynamic Proggramming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理·生产调度·工程技术和最优控制等方面得到了广泛的应用。例如最短路线·库存管理·资源分配·设备更新·组合·排序·装载等问题，采用动态规划法求解比用其他方法更为简便。 二·动态规划法基本概念 一个多阶段决策过程最优化问题的动态规划模型通常包括以下几个要素： 1．阶段 阶段（stage）是对整个过程的自然划分。通常根据时间顺序或是空间特征来划分阶段，对于与时间，空间无关的“静态”优化问题，可以根据其自然特征，人为的赋予“时段”概念，将静态问题动态化，以便按阶段的顺序解优化问题。阶段变量一般用k=1.2….n.表示。
1.状态 状态(state)是我们所研究的问题（也叫系统）在过个阶段的初始状态或客观条件。它应能描述过程的特征并且具有无后效性，即当某阶段的状态给定时，这个阶段以后的过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是可以直接或者是间接可以观测的。描述状态的变量称为状态变量（State Virable）用s 表示，状态变量的取值集合称为状态集合，用S表示。变量允许取值的范围称为允许状态集合(set of admissble states).用x(k)表示第k阶段的状态变量，它可以是一个数或者是一个向量。用X(k)表示第k阶段的允许状态集合。 n 个阶段的决策过程有n+1个状态变量，x(n+1)是x(n)的演变的结果。 根据演变过程的具体情况，状态变量可以是离散的或是连续的。为了计算方便有时将连续变量离散化，为了分析的方便有时又将离散的变量视为连续的。 2．决策 当一个阶段的状态确定后，可以做出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision），在最优控制问题中也称为控制（control）描述决策的变量称为决策变量（decision virable）。变量允许取值的范围称为允许决策集合（set of admissble
状态压缩dp 炮兵阵地 Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 8971 Accepted: 3169 Description 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示： 如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。 Input 第一行包含两个由空格分割开的正整数，分别表示N和M； 接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。 Output 仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。 Sample Input 5 4
PHPP PPHH PPPP PHPP PHHP Sample Output 6 Source Noi 01 这道题是一道典型的状态压缩DP。 注意到每一行炮兵的摆放只和前两行有关系，便可以记录一个f数组，f[h,i,j]表示第h行的状态为st[i]，第h-1行的状态为st[j]。 现在的关键就是如何快速求f[h,i,j]。 注意到求f数组跟状态数有关，那么便优化状态。 首先是状态的存储。注意到m范围较小，便可以按行存储。对于每一行，如果一个格子放了炮兵，就看成1，否则看成0，然后记下对应数列的十进制值即可。但这样共有2^m种状态，显然太多了。注意到有很多状态其实是不可能的(即某个炮兵附近还有炮兵)，我们就可以再预处理状态时加一些判断。那么如何高效判断呢？对了，可以用位运算！ 判断过程如下： for i:=0 to 1 shl m-1 do begin if i and (i shl 1)<>0 then continue;//错一位进行判断 if i and (i shl 2)<>0 then continue;//错两位进行判断 inc(sl); st[sl]:=i; count[sl]:=calc(i);//count数组记录每个序列中1的个数 end; 解决了存储问题后，整个程序就很简单了，剩下的DP不再赘述，详见程序。贴代码：https://www.doczj.com/doc/9f9767695.html,/code/view/18264/ var f:array[1..100,1..70,1..70] of integer; map:array[1..100] of integer; st,count:array[1..70] of integer; n,m,sl:integer; function calc(x:integer):integer; var sum:integer;
动态规划经典教程 引言：本人在做过一些题目后对DP有些感想，就写了这个总结： 第一节动态规划基本概念 一，动态规划三要素：阶段，状态，决策。 他们的概念到处都是，我就不多说了，我只说说我对他们的理解： 如果把动态规划的求解过程看成一个工厂的生产线，阶段就是生产某个商品的不同的环节，状态就是工件当前的形态，决策就是对工件的操作。显然不同阶段是对产品的一个前面各个状态的小结，有一个个的小结构成了最终的整个生产线。每个状态间又有关联（下一个状态是由上一个状态做了某个决策后产生的）。 下面举个例子： 要生产一批雪糕，在这个过程中要分好多环节：购买牛奶，对牛奶提纯处理，放入工厂加工，加工后的商品要包装，包装后就去销售……，这样没个环节就可以看做是一个阶段；产品在不同的时候有不同的状态，刚开始时只是白白的牛奶，进入生产后做成了各种造型，从冷冻库拿出来后就变成雪糕（由液态变成固态=_=||）。每个形态就是一个状态，那从液态变成固态经过了冰冻这一操作，这个操作就是一个决策。 一个状态经过一个决策变成了另外一个状态，这个过程就是状态转移，用来描述状态转移的方程就是状态转移方程。 经过这个例子相信大家对动态规划有所了解了吧。 下面在说说我对动态规划的另外一个理解： 用图论知识理解动态规划：把动态规划中的状态抽象成一个点，在有直接关联的状态间连一条有向边，状态转移的代价就是边上的权。这样就形成了一个有向无环图AOE网（为什么无环呢？往下看）。对这个图进行拓扑排序，删除一个边后同时出现入度为0的状态在同一阶段。这样对图求最优路径就是动态规划问题的求解。 二，动态规划的适用范围 动态规划用于解决多阶段决策最优化问题，但是不是所有的最优化问题都可以用动态规划解答呢？ 一般在题目中出现求最优解的问题就要考虑动态规划了，但是否可以用还要满足两个条件： 最优子结构（最优化原理） 无后效性 最优化原理在下面的最短路径问题中有详细的解答； 什么是无后效性呢？ 就是说在状态i求解时用到状态j而状态j就解有用到状态k…..状态N。 而求状态N时有用到了状态i这样求解状态的过程形成了环就没法用动态规划解答了，这也是上面用图论理解动态规划中形成的图无环的原因。 也就是说当前状态是前面状态的完美总结，现在与过去无关。。。 当然，有是换一个划分状态或阶段的方法就满足无后效性了，这样的问题仍然可以用动态规划解。 三，动态规划解决问题的一般思路。 拿到多阶段决策最优化问题后，第一步要判断这个问题是否可以用动态规划解决，如果不能就要考虑搜索或贪心了。当却定问题可以用动态规划后，就要用下面介绍的方法解决问题了：（1）模型匹配法： 最先考虑的就是这个方法了。挖掘问题的本质，如果发现问题是自己熟悉的某个基本的模型，就直接套用，但要小心其中的一些小的变动，现在考题办都是基本模型的变形套用时要小心条件，三思而后行。这些基本模型在先面的分类中将一一介绍。 （2）三要素法 仔细分析问题尝试着确定动态规划的三要素，不同问题的却定方向不同： 先确定阶段的问题：数塔问题，和走路问题（详见解题报告） 先确定状态的问题：大多数都是先确定状态的。 先确定决策的问题：背包问题。（详见解题报告） 一般都是先从比较明显的地方入手，至于怎么知道哪个明显就是经验问题了，多做题就会发现。 （3）寻找规律法： 这个方法很简单，耐心推几组数据后，看他们的规律，总结规律间的共性，有点贪心的意思。 （4）边界条件法 找到问题的边界条件，然后考虑边界条件与它的领接状态之间的关系。这个方法也很起效。 （5）放宽约束和增加约束 这个思想是在陈启锋的论文里看到的，具体内容就是给问题增加一些条件或删除一些条件使问题变的清晰。 第二节动态规划分类讨论
信息学竞赛中的动态规划专题 哈尔滨工业大学周谷越 【关键字】 动态规划动机状态典型题目辅助方法优化方法 【摘要】 本文针对信息学竞赛（面向中学生的Noi以及面向大学生的ACM/ICPC）中的动态规划算法，从动机入手，讨论了动态规划的基本思想和常见应用方法。通过一些常见的经典题目来归纳动态规划的一般作法并从理论上加以分析和说明。并介绍了一些解决动态规划问题时的一些辅助技巧和优化方法。纵观全文可知，动态规划的关键在于把握本质思想的基础上灵活运用。 【目录】 1.动态规划的动机和基本思想 1.1.解决重复子问题 1.2.解决复杂贪心问题 2.动态规划状态的划分方法 2.1.一维状态划分 2.2.二维状态划分 2.3.树型状态划分 3.动态规划的辅助与优化方法 3.1.常见辅助方法 3.2.常见优化方法 4.近年来Noi动态规划题目分析 4.1 Noi2005瑰丽华尔兹 4.2 Noi2005聪聪与可可 4.3 Noi2006网络收费 4.4 Noi2006千年虫 附录参考书籍与相关材料
1.动态规划的动机和基本思想 首先声明，这里所说的动态规划的动机是从竞赛角度出发的动机。 1.1 解决重复子问题 对于很多问题，我们利用分治的思想，可以把大问题分解成若干小问题，然后再把各个小问题的答案组合起来，得到大问题的解答。这类问题的共同点是小问题和大问题的本质相同。很多分治法可以解决的问题（如quick_sort，hanoi_tower等）都是把大问题化成2个以内的不相重复的小问题，解决的问题数量即为∑(log2n / k)。而考虑下面这个问题： USACO 1.4.3 Number Triangles http://122.139.62.222/problem.php?id=1417 【题目描述】 考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每一步可以走到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 1 在上面的样例中，从7到3到8到7到5的路径产生了最大和：30。 【输入格式】 第一个行包含R(1<= R<=1000) ,表示行的数目。后面每行为这个数字金字塔特定行包含的整数。所有的被供应的整数是非负的且不大于100。 【输出格式】 单独的一行包含那个可能得到的最大的和。 【样例输入】 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 1 【样例输出】 30 显然，我们同样可以把大问题化成小问题来解决。如样例中最底层的6就可以从次底层