Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### khatribiru's blog

By khatribiru, history, 3 years ago, ,

This Blog is Just the List of Problems for Dynamic Programming Optimizations.Before start read This blog.

#### 3. Convex Hull Trick Technique(CHT)

Note:- Some problems from Divide and conquer optimization section can also be solved using CHT.

• +199

 » 3 years ago, # |   +8 Link to Problem 1 and Problem 4 on Divide and Conquer Opt point to the same problem
•  » » 3 years ago, # ^ |   +27 Edited :- Thank You .
 » 3 years ago, # |   +4 two more problems for CHT :
•  » » 3 years ago, # ^ |   +11 Added. Thank You.
 » 3 years ago, # |   +8 I think in Divide and Conquer Optimization article there was written dp[i−1][j]+C[k][j] i think it should be dp[i−1][k]+C[k][j]?
•  » » 3 years ago, # ^ |   +11 Yes You are correct. The fifth line of first paragraph there should be dp[i−1][k]+C[k][j].
 » 3 years ago, # |   0 Another one: Ciel and Gondolas
•  » » 3 years ago, # ^ |   +13 Look Problem 5. Which was same as you given.
 » 3 years ago, # |   +6 Nice Collections , Liked it.
•  » » 3 years ago, # ^ |   +7 Thanks.
 » 3 years ago, # |   +4 Thanks a lot bro . Was searching for something like this . :)
 » 3 years ago, # |   +5 Another problem that can be solved using D&C: ARC 067 problem F
•  » » 2 years ago, # ^ |   0 Added. Thank You.
 » 3 years ago, # |   0 Where can we submit solutions to the above problems from Russian Camp.
 » 2 years ago, # |   0 One more problem of Divide and Conquerhttp://codeforces.com/problemset/problem/834/D
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 POJ 1741 is solvable with Tree/Sibling Dp + Divide and Conquer. If it suits, it can be added.
•  » » » 2 years ago, # ^ |   0 Added. Thank You.
•  » » 2 years ago, # ^ |   0 Added. Thank You.
 » 2 years ago, # |   0 There is also a very cool technique to optimize DP. I have seen it in a Radewoosh comment here and in a recent CSAcademy contest here.
 » 2 years ago, # |   0 Auto comment: topic has been updated by khatribiru (previous revision, new revision, compare).
 » 23 months ago, # |   0 Fresh problem. Can be solved with CHT.
 » 11 months ago, # |   0 Thanks
 » 7 months ago, # |   0 From Codechef Long Challenge July19 Can be solved using CHT