动态规划

题单
阅读体验：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
  
  • 洛谷P2513 [HAOI2009]逆序对数列
  • 洛谷P2511 [HAOI2008]木棍分割
  • 洛谷P4099 [HEOI2013]SAO
  • 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
  
  • 洛谷P1886 滑动窗口(单调队列入门)
  • 洛谷P1776 宝物筛选_NOI导刊2010提高(02)(多重背包单调队列优化)
  • 洛谷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]柠檬
  • 洛谷P3515 [POI2011]Lightning Conductor
  • 洛谷P1912 [NOI2009]诗人小G
  • CF868F Yet Another Minimization Problem（洛谷）（vjudge）

斜率优化

简述

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

题目

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

状压dp

题目

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

区间dp

题目

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

树形dp

题目

• By Myself
  
  • P3177 [HAOI2015]树上染色