← 返回 walmartlabs 的题目列表Trekking in a Mountain Range
类型:online_judge
You are hiking in a mountainous area, where each point on the path has a base elevation base[i]. Each day, different points may experience snowfall, accumulating on top, thus increasing the current elevation. The snowfall amounts are given by a matrix snow[day][i] where snow on day day at point i is recorded. If there is no snowfall for a continuous 2 days, the snow on that point starts to melt at a rate of 1 cm per day, until it reaches 0. Current elevation = base[i] + accumulated snow.
While hiking from the start at 0 to the finish at n-1, the current elevation must not be more than the previous one plus 1 (i.e., it can ascend by at most 1). Each time you go from i-1 to i, any elevation increase demands climbing effort. Find the earliest day that makes the entire route feasible with minimal climbing sum.
Example
Input
4
3 1 2 1
1 0 0 1
0 1 0 1