(想來想去還是先弄DP計算幾何就先放放) 1,、背包模型包括0-1背包、無限背包,、有限背包,、有價值背包、小數(shù)背包(貪心即可)等,,是極為經(jīng)典的模型,,其轉(zhuǎn)化與優(yōu)化也是很重要的。H P4^ k v3T V A 2,、最長非降子序列模型 7i _ F+E N H g O8| | | s 改版:渡河問題,、合唱隊型等 3、最大子段和模型 改版:K大子段和,、最佳游覽,,最大子矩陣和等。 4,、LCS模型 ?:p0n E m$v |+r 改版:回文字串,、多串的LCS等 5、括號序列模型 M Y3e V D:D 改版:關(guān)燈問題(TSOJ),、charexp(TSOJ)、最大算式等,,核心思想在于以串的長度為階段,。 6、遞推模型 p:l s#U i _1J L } 這類題是屬于徘徊在DP與遞歸之間得一類題,,本質(zhì)是類似于記憶化搜索的一種填表,,有很強的數(shù)學(xué)味。 &e n o A:l V 7,、線段覆蓋問題 改版:Tom的煩惱(TOJ)等,。經(jīng)常利用到離散化等技巧輔助。 ^'g R V1e+h&F 8,、單詞劃分模型 和LCS基本上構(gòu)成了字符串DP的主要類型,。改版:奇怪的門(TOJ)等。 9,、股票模型 8u F.[ x&m |8g!{ 這是DP優(yōu)化的經(jīng)典模型,。改版有換外匯等。 ,o/z yw ?5\/d 10,、連續(xù)段劃分模型 即要求把數(shù)列劃分成k個連續(xù)段,,使每段和的最大值最小。改版有任務(wù)調(diào)度等,。 x0e B6d k X j8t'v1| Y 11,、游戲模型 這類題的階段(一般是時間)和決策(一般就是游戲目標)很清楚,,因此比較容易想到。改版:免費餡餅(NOI98),、Help Jimmy(CEOI2000),、瑰麗華爾茲(NOI2005,優(yōu)化需要多費功夫),。 y KY/\ |
|
來自: dinghj > 《基礎(chǔ)-算法》