Решение задачи Петя и деревня с Codeforces
С пояснением   Просмотров: 59
Маленький Петя часто ездит к бабушке в деревню. У бабушки есть большой огород, который, если смотреть сверху, можно представить в виде прямоугольника размером 1 × n, разбитого на n одинаковых квадратных участков. Особенностью огорода является то, что каждый из квадратных участков имеет свою фиксированную высоту и над каждым из участков при помощи новейшей системы водоснабжения может быть создан искусственный дождь над этим участком.
Создание искусственного дождя — дорогостоящая операция, поэтому мы ограничимся тем, что искусственный дождь будет создан лишь над одним участком. При этом вода с каждого затопленного участка будет попадать на соседние с ним участки, если их высота не превосходит высоту данного участка. То есть, к примеру, если огород представляет собой прямоугольник 1 × 5, где высоты участков равны 4, 2, 3, 3, 2, то создав искусственный дождь над любым из участков с высотой 3 — вода разольется по всем участкам, кроме участка с высотой 4. Картинка, поясняющая этот пример:
Петя увлекается программированием, поэтому он решил найти такой участок, что если мы создадим над этим участком искусственный дождь, то количество участков, на которые попадет вода, будет максимальным. Помогите ему.
Создание искусственного дождя — дорогостоящая операция, поэтому мы ограничимся тем, что искусственный дождь будет создан лишь над одним участком. При этом вода с каждого затопленного участка будет попадать на соседние с ним участки, если их высота не превосходит высоту данного участка. То есть, к примеру, если огород представляет собой прямоугольник 1 × 5, где высоты участков равны 4, 2, 3, 3, 2, то создав искусственный дождь над любым из участков с высотой 3 — вода разольется по всем участкам, кроме участка с высотой 4. Картинка, поясняющая этот пример:
Петя увлекается программированием, поэтому он решил найти такой участок, что если мы создадим над этим участком искусственный дождь, то количество участков, на которые попадет вода, будет максимальным. Помогите ему.
Пояснение к задаче
Тут нужно перебрать все возможные позиции для создания искусственного дождя, посмотреть сколько в каждом из случаев получается участков, содержащих воду и выбрать среди всех возможных вариантов максимальный. При этом подсчитывать ответ для текущей позиции будем, просто расходясь вправо и влево от текущей позиции. Итоговая сложность O(N^2).