规律-
[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 ?/?cat=5
[2]
动态规划方法总结
1.
按状态类型分
写在前面:
从状态类型分,
并不表示一题只从属于一类。
其实一类 只是一种状态的表示方法。
可以好几
种方法组合成一个状态,来解决问题。
1.1.
编号(长度)动态规划
共性总结:
本类的状态是基础的基础,大部分的动态规划都要用到它,成为一个维。一般来说,有两种
编号的状态 :
1
、状态
(i)
表示前
i
个元素决策组成的一 个状态。
2
、状态
(i)
表示用到了第
i
个元素 ,和其他在
1
到
i-1
间的元素,决策组成有的一个状态。
题库:
a)
最长不下降子序列
以一元组< br>(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)|
是单调的,< br>所以取中位数就可以了。
即上式中
k
的取值范围只有
floor((i+j)/2),
ceil((i+j)/2)
两个。
Fl oor
是下取整。
Ceil
是上取整。这样每次转移时间降到
O(1)
。注意到是区
间连续的,即
(p,i-1)
和
(i, j)
中的
i-1, i
是连续的,所以空间可以降维:
f(i,j)< br>表示放前
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,y 1)(x2,y2)
,表示一个子棋盘。这有点像之前的区间动态规划,只不过是将
1
维转
2
维。
后见路径问题。
1.4.
数轴动态规划
规律-
规律-
规律-
规律-
规律-
规律-
规律-
规律-
本文更新与2021-01-22 03:52,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/547955.html
-
上一篇:学生成绩管理系统说明书
下一篇:英文陆空对话范例--飞行员必备