As the problem requires, we first check the suits of the given two cards. If they have the same suit, then we compare their ranks; otherwise we check whether the first card is the the trump card or not.
We can adopt a double loop to eliminate all the outdated laptops. Next, we find the cheapest one as the answer.
At first, I tried to solve it based on greedy algorithm. However, it turns out that such a greedy algorithm fails since all the involved numbers are integers...
Well, this is essentially a backpack problem, if we implement some equivalent transformation. More specifically, it is a multiple-backpack problem, one can also check the one in 95E - Счастливая страна, which is also solved based on multiple-backpack.
The solution is straightforward implementation. However, trivial implementation ends up with TLE. To avoid this, for each position, we should calculate in previous the farthest position that we can reach when we move to any one of the four directions. This can be computed by using DP algorithm with complexity O(mn).
Comments (0)
