I am struggling with this problem: https://dunjudge.me/analysis/problems/896/

It is suggested on cp-algorithms.com that convex hull trick can solve this problem. I read this problem a month ago and now come back to it I still cannot solve it.

Can anyone help me with this, Thanks in advance.

You need a couple of observations:

First, if there are some cats $$$i, j$$$ such that $$$a_i \le a_j$$$ and $$$b_i \le b_j$$$ then it's optimal to put the cat $$$i$$$ on the same group as cat $$$j$$$. We can ignore the cat $$$i$$$. Therefore we can sort all cats by $$$(a_i, b_i)$$$ and erase all these "useless" cats, getting at the end an array where the cats are sorted strictly increasing by $$$a_i$$$ and strictly decreasing by $$$b_i$$$.

Other observation: now with this new array, it's optimal to group consecutive cats.

Therefore now you can use the following DP:

$$$dp[i]$$$: min cost of partitioning the prefix until position $$$i$$$. The transitions are:

Now you can apply easily

Convex Hull Trickhere. You can get linear complexity, because the slopes are sorted and the points of the queries to your DS are sorted too.Gee, I came up with part of the first observation but didn't think of erasing all the useless cats. Thanks for your explanation.