How to solve this DP problem from 2019-20 ICPC Brazil Subregional programming contest

Revision en3, by toxic_hack, 2020-04-27 10:42:20

I have been trying to solve (Kth problem in the pdf) this problem for a couple of days. I find this problem very hard and the DP states and transitions are too confusing for me. I don't know how to go about thinking these types of problems :( Can someone please explain how to approach this problem? It will be very helpful.

Tags #acm-icpc, brazil, #dynamic programing, matrices

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English toxic_hack 2020-04-27 10:42:20 62 Tiny change: 'h problem the pdf)[this](htt' -> 'h problem in the pdf) [this](htt'
en2 English toxic_hack 2020-04-26 23:10:12 21 Tiny change: ' to solve [this](htt' -> ' to solve (Kth problem the pdf)[this](htt'
en1 English toxic_hack 2020-04-26 22:47:23 375 Initial revision (published)