动态规划总结

动态规划

标签: 题单
阅读体验：https://zybuluo.com/Junlier/note/1285305

(Anson)爷的动态规划

(cj)的同学去这里

(fdf)总结的题单

还是只有(cj)的同学能去啊

其他

部分题目是(Flash Hu)给的谢谢
ps：简述是我自己的感受QwQ。。。虽然%(Flash)%更强也写的更好。。。
其实没必要区分那么多的啦
反正机房团结，我的就是大家的对吧

前缀和优化dp

简述

当dp转移式是由上一个状态的一段区间和转移过来时，可以考虑前缀和优化dp
形如 (f[i][j]+=sum_{k=p}^{q}f[i-1][k])
可以对(i)所有的(f[i][j])记一个前缀和 (g[i][j]=g[i][j-1]+f[i][j])
那么转移可以优化成 (f[i][j]+=g[i-1][q]-g[i-1][p-1])

题目

• [ ] By Flash
  • [x] 洛谷P2513 [HAOI2009]逆序对数列
  • [x] 洛谷P2511 [HAOI2008]木棍分割
  • [ ] 洛谷P4099 [HEOI2013]SAO
  • [x] NOIAC37 染色(后缀和优化)
• [ ] By Myself
  • [ ] 洛谷P2280 [HNOI2003]激光炸弹

单调队列优化dp

简述

我觉得单调队列优化(dp)好难。。。是我太蒻了。。。

1. 当一个状态是由一段区间的最大(dp)值转移过来时
2. 当那一段区间的(dp)值随下标单调时

可以用单调队列省去枚举那一段([p,q])找最大值的复杂度
形如(dp[i][j]=Max_{k=p}^{q}{dp[i-1][k]}+Others)
可以在枚举(j)的过程中把(dp[i-1][k])丢到优先队列里面去，然后一边丢一边维护，一边转移一边维护

题目

• [ ] By Flash
  • [x] 洛谷P1886 滑动窗口(单调队列入门)
  • [x] 洛谷P1776 宝物筛选_NOI导刊2010提高(02)(多重背包单调队列优化)
  • [x] 洛谷P2254 [NOI2005]瑰丽华尔兹
  • [ ] 洛谷P2569 [SCOI2010]股票交易
  • [ ] 洛谷P3572 [POI2014]PTA-Little Bird
  • [ ] 洛谷P3594 [POI2015]WIL-Wilcze doły
• [ ] By Myself
  • [ ] P2954 [USACO09OPEN]移动牛棚Grazing2
  • [ ] P3089 [USACO13NOV]POGO的牛Pogo-Cow

决策单调性优化

二分栈

• [ ] By Flash
  • [ ] 洛谷P1973 [NOI2011]Noi嘉年华
  • [ ] 洛谷P3724 [AH2017/HNOI2017]大佬

分治

• [ ] By Flash
  • [ ] BZOJ4709 [Jsoi2011]柠檬
  • [x] 洛谷P3515 [POI2011]Lightning Conductor
  • [ ] 洛谷P1912 [NOI2009]诗人小G
  • [ ] CF868F Yet Another Minimization Problem（洛谷）（vjudge）

斜率优化

简述

看下面题目里的土地征用的solution吧。。。

题目

• [ ] By Flash
  • [x] 洛谷P2900 [USACO08MAR]土地征用Land Acquisition
    solution
  • [x] 洛谷P3195 [HNOI2008]玩具装箱TOY
  • [x] 洛谷P3628 [APIO2010]特别行动队
  • [x] 洛谷P4360 [CEOI2004]锯木厂选址
  • [ ] 洛谷P2305 [NOI2014]购票
  • [ ] 洛谷P1721 [NOI2016]国王饮水记

状压dp

题目

• [ ] By Myself
  • [x] P2915 [USACO08NOV]奶牛混合起来Mixed Up Cows
  • [ ] P3475 [POI2008]POD-Subdivision of Kingdom
  • [x] P3052 [USACO12MAR]摩天大楼里的奶牛Cows in a Skyscraper
  • [x] [USACO06NOV]玉米田Corn Fields
  • [ ] P3087 [USACO13NOV]农民约翰没有大棕牛Farmer John has no Large Brown Cow
  • [x] P1896 [SCOI2005]互不侵犯
  • [x] P3092 [USACO13NOV]没有找零No Change
  • [ ] P3070 [USACO13JAN]岛游记Island Travels
  • [ ] P2595 [ZJOI2009]多米诺骨牌
  • [x] P2704 [NOI2001]炮兵阵地
  • [x] P2051 [AHOI2009]中国象棋

区间dp

题目

• [ ] By Myself
  • [x] CF567F Mausoleum
  • [x] UVA10559 Blocks
  • [x] [USACO06FEB]奶牛零食Treats for the Cows
  • [x] P3205 [HNOI2010]合唱队
  • [ ] P2470 [SCOI2007]压缩
  • [x] P2466 [SDOI2008]Sue的小球