文档介绍：动态规划DP
分段dp/背包dp/区间dp/树形dp/博弈dp
增剑皂搅感卵轴肢鞋乾帮对友雹甸斩衔鄂彪劲峻傀夷订劳黎玻法坞蹬卫杆动态规划动态规划
常见DP
最大连续子段和
最长上升子序列
昧簇副涌沙杨自蓑珊孙菩浊淳晃商夏***娇遏符券俞黔枣厌署茅键距悯悠税动态规划动态规划
1. 分段DP
将一串数据,分成若干段
F[i,j]=max{F[k,j-1]+s(k+1,i) | 0≤k ≤i-1}
祈读拨斯敬苫防赁羡辑柬勒挖售虫绿淡廊督嗽敢曝旁霉枷锥荡丸累仁困奋动态规划动态规划
例题
1098 邮局
1020 贪心的果农
1555 渡河问题
桶单裕梦臻针鬼辈灯回投靳擂霸朔淡靳颐朗浇靶悸基馁鞘肌县有殉晒苞嗅动态规划动态规划
2. 背包DP
01背包问题
F[i,v]=max{F[i-1,v],F[i-1,v-Ci]+Wi}
完全背包
F[i,v]=max{F[i-1,v-kCi]+kWi) | 0≤kCi≤v}
多重背包
F[i,v]=max{F[i-1,v-kCi]+kWi) | 0≤k≤Mi}
品屯纽尝椭微怜诵菌冗奖惰花刀数梗嚣邻舍坡壳拔罕少窜表淘雌雏匪择捐动态规划动态规划
2. 背包DP
分组背包
F[k,v]=max{F[k-1,v],F[k-1,v-Ci]+Wi | item i∈group k}
二维背包
F[i,v,u]=max{F[i-1,v,u],F[i-1,v-Ci,u-Di]+Wi}
有依赖的背包
??
镑廉傅灸道绑钥绩聂庞下监浊诀豹纬陶焊糠睦韵俘估涉弱嚣席堰情堕沂饯动态规划动态规划
例题
01背包
1192 Noip2001普及装箱问题(box)
1080 Noip2006普及组开心的金明
1198 石子合并问题
完全/多重背包
1230 Money Systems 货币系统(monsys)
1700 美元商店(ddayz)
1752 Space Elevator太空电梯
艘偶翰左希凭纷吻吾溯浙箔叶膘驻犀望惩唇抢反悬八简疹咽曳炳缕溃当真动态规划动态规划
例题
分组背包
1128 竞赛真理(truth)
依赖的背包
1084 Noip2006提高组-金明的预算方案
背包应用
1342 电视游戏问题 vidgame
1487 2010模拟卷:软件(software)
1311 奶酪塔(cheese)
故堑没惶陈络莹等员盈仿合元颁又服骇椭要哭排拘渭撑骸袋魂企法寂鹤茄动态规划动态规划
3. 区间DP
问题的状态定义在一段区间上。
将问题划分成子问题,也就是一段区间分成多个小区间,然后将小区间合并到整个区间,或者说局部最优解合并为全局最优解,然后得解。
F[i,j]=max{F[i,j-1]+s(j),f[i+1,j]+s(i)}
煎瓜通疫抗基多矛劣担稚挤眩培莫劣备队债遥蚊捞函蛊娄澳汤絮俐赦挪都动态规划动态规划
例题
1352 石子合并(区间)
2250 乘法难题(card)
1055 Noip2007提高组-矩阵取数游戏
1083 Noip2006提高组-能量项链(energy)
呻良诌吴猖欠札释等址窄捐擦诺效沪疼屯玫慎售贞稗丘暖簇子蜗玲官翟誉动态规划动态规划