Editorial for COCI '08 Contest 1 #5 Skakavac
Submitting an official solution before solving the problem yourself is a bannable offence.
Suppose first that the grasshopper can jump to any flower in the neighbouring rows and columns.
We can use dynamic programming to solve the problem. First sort the flowers by numbers of petals. For each flower , we calculate , the largest number of flowers the grasshopper can visit if it starts at flower . We calculate this by considering all flowers in the neighbouring rows and columns; then .
To calculate more quickly, we can keep track of the largest value for each row and column.
If we reintroduce the restriction from the problem statement on which flowers the grasshopper can jump to, this last improvement no longer works, since the grasshopper may not be allowed to jump to the best flower in a row or column. However, keeping track of the four best flowers in a row or column will do because at most three flowers in a row or column are forbidden.
Comments