DP Optimizations, Centroid, Knuth, CHT, 1D1D, Fractional Cascading materials

DP Optimizations:

http://codeforces.com/blog/entry/8219

Divide and Conquer DP:

Links from above blog

Knuth Optimization:

https://www.quora.com/What-is-Knuths-optimization-in-dynamic-programming

http://www.cse.ust.hk/~golin/COMP572/Notes/DP_speedup.pdf

http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/p429-yao.pdf

Convex Hull Trick:

CHT

1D-1D:

https://sites.google.com/site/ubcprogrammingteam/news/1d1ddynamicprogrammingoptimization-parti

Some relevant problems:

Commando APIO 2010

Exchange NOI 2007

Breaking Strings http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1860

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3983

Little G the poet NOI 2009

Holiday IOI 2014

Split The Sequence APIO 2014

Fractional Cascading:

http://blog.ezyang.com/2012/03/you-could-have-invented-fractional-cascading/

http://blog.ezyang.com/2012/02/visualizing-range-trees/

Maximum Flow:

https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-section-1/

Centroid Decomposition:

https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree

http://petr-mitrichev.blogspot.com/2015/03/this-week-in-competitive-programming_22.html

http://codeforces.com/blog/entry/10533#comment-159119