I am trying to do the USACO training, which has the exact same
problem. I have no idea how to proceed to solve it, and without
solving it, I cannot advance in the training!

Can anyone give me any hints on how to approach the problem?

There are many method to solve this problem. I'm not introducing the
best one. But you will be able to pass this problem at USACO with it for
sure.

At first , try to solve the problem 1019 : Line Painting or 105-Sky Line at
Valladolid (acm.uva.es). You'll find something useful ;)