关键词不能为空

当前您在: 主页 > 英语 >

fdi是什么意思poj dp题目列表

作者:高考题库网
来源:https://www.bjmy2z.cn/gaokao
2021-01-22 03:46
tags:

eight-

2021年1月22日发(作者:大虾)
[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


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.
数轴动态规划

共性总结:


题库:


a) 01
背包


应用:

装箱问题(
NOIP01 Trade 4


就是原题。

eight-


eight-


eight-


eight-


eight-


eight-


eight-


eight-



本文更新与2021-01-22 03:46,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/547930.html

poj dp题目列表的相关文章