DP的优化总结

一、预备知识

二、优化方法

1. 利用决策单调性

2. 分治优化

相关文章：post1

3. 单调队列

4. 斜率优化

相关文章： bzoj1492 [NOI2007]货币兑换Cash

5. 凸包优化（Convex Hull Trick）

相关文章：Convex hull trick

6. 凸包优化2

相关文章: post2

7. Knuth优化

相关文章：1 2

三、题目

凸包优化（CHT）

1. BZOJ 1701-Cow School Solution-Video
2. SPOJ-APIO2010 Commando
3. SPOJ-TRAKA
4. SPOJ-BAABO
5. SPOJ-ACQUIRE
6. SPOJ-NKLEAVES
7. cf91e-SkyScrapers (+Data Structures)
8. cf311b Cats Transport
9. cf660f Bear and Bowling 4
10. cf319c Kalila and Dimna in the Logging Industry
11. cf631e Product Sum
12. cf455e Function
13. cf536c Tavas and Pashmaks
14. cf377e Cookie Clicker
15. cf91e Igloo Skyscraper
16. Jump mission | CodeChef
17. Contest Page | CodeChef

Knuth 优化

1. Spoj-BRKSTRNG
2. UVa10003-Cutting Sticks
3. UVa10304
4. Order-Preserving Codes - gym100212C
5. UVa12057
6. UVa-12836

分治优化

1. cf321e Ciel and Gondolas
2. hr-Guardians of the Lunatics
3. Chef and Bitwise OR Operation | CodeChef
4. SPOJ-NKLEAVES
5. hr-mining
6. Bicolored Horses
7. UVa12524
8. cf673e Levels and Regions
9. ARC 067D

斜率优化

1. BZOJ 1597 [Usaco2008 Mar]土地购买
2. BZOJ 3675 [APIO 2014]序列分割
3. BZOJ 1010 [HNOI2008]玩具装箱toy
4. BZOJ 3437 小P的牧场
5. BZOJ 3156 防御准备
6. BZOJ 1096 [ZJOI2007]仓库建设
7. BZOJ 1911 APIO 2010 Commando
8. BZOJ 4518 [SDOI2016] 征途
9. HDU 3507
10. HDU 3401
11. HDU 2191
12. HDU 5956 The Elder

平衡树维护动态凸包

1. cf70d
2. BZOJ 2300(HAOI2011)防线修建
3. BZOJ 1492 货币兑换Cash
4. HDU 5127 Dogs’ Candies

参考文章：

1. Dynamic programming with convexity, concavity and sparsity
2. 《算法艺术与信息学竞赛》p149。
3. 1D1D动态规划优化初步
4. 动态规划算法的优化技巧-毛子青
5. dp优化-个人对dp优化的理解
6. Dynamic Programming Optimizations
7. 斜率优化 二