Problem Link - Planet
Problem Statement
On a certain planet, there are n regions in a line, numbered from 1 to n. In the $i$th of these regions resides a species where each organism has weight w_i, as well as enough resources to support a_i organisms.
You are tasked with placing k walls to separate the planet into k+1 segments. Each wall should be placed between two regions i and i+1, where 1 \leq i \leq n-1, and all walls should be placed in different positions. After you place the walls, the following happens in each segment:
- The species with the highest w_i wins and kills all other species in the segment, thus taking control of the whole segment.
- Over time, this species uses up all the resources of the segment, and thus the number of organisms of the winning species becomes equal to the sum of a_i in the segment.
Define the \textit{biomass} of the planet as the sum of the weights of all the organisms living on the planet. You don’t like life, so your goal is to place the k walls to \textit{minimise} the biomass. What is the minimum value you can achieve?
approach
To solve the problem, the logic is to break the regions into segments by placing k walls between them in such a way that the biomass (the total weight of organisms) is minimized. The approach involves dynamic programming where we try to minimize the biomass by calculating the effect of placing each wall and forming segments. The idea is to look at each possible segment and compute the total weight of organisms after considering the species with the maximum weight in that segment. By doing this iteratively and considering all possible placements of walls, we can determine the optimal placement that minimizes the biomass. The dynamic programming array stores the minimum biomass achievable for each number of walls and regions. We calculate the possible biomass for each segment and use previously computed values to get the minimum value for all segments, leading us to the optimal solution.
Time complexity
The time complexity of this solution is O(n^2 \times k) where n is the number of regions and k is the number of walls to place.
Space complexity
The space complexity is O(n \times k) due to the storage of the dynamic programming table.