dp任务清单

清单

数位dp

• 三素数
• 三素数(数据加强版)

斜率优化(戳我寻找更多题目)

• 玩具装箱
• 特别行动队
• [SCOI2010]股票交易
• [APIO2014]序列分割
• [ZJOI2007]仓库建设
• [NOI2005]瑰丽华尔兹

总结

请注意常见形式:一旦出现两个斜率时是不可做的
如果x不是单调的，那我们使用CDQ分治来计算,听说树状数组太慢了
如果是树上问题我们再来个点分治

状压dp

• 没有找零No Change
• 子矩阵
• 小笼包
• 宝藏
• [SDOI2009]Bill的挑战
• [THUWC2017]随机二分图(真TM神仙题)

树形dp

• [HAOI2015]树上染色
• 城市环路

字符串dp

区间dp

• [SDOI2008]Sue的小球

期望dp(没有严格按照难度添加)

• 彩色圆环
• [UVa11021]麻球繁衍
• [UVA11427]Expect the Expected
• OSU!
• [NOI2005]聪聪与可可
• [HDU6229]Wandering Robots
• [SHOI2002]百事世界杯之旅
• 小魔女帕琪
• [SCOI2008]奖励关
• [UVALive4297]First Knight
• [国家集训队]单选错位
• [CTSC2006]歌唱王国

总结

对于终止状态唯一确定时，要倒着做dp

排序(贪心)dp

• [ZJOI2005]午餐

神尼码dp

• 新魔法药水
• 小a和小uim大逃离(数据加强版)
• 跳舞(数据加强版)