Вопрос жизни и смерти

Правка ru1, от moskalenco_a, 2016-11-21 04:46:57

Доброго времени суток всем кто читает этот пост. Читая одну книжку по ДП столкнулся с очень сложной проблемой. Для того чтобы эффективно решать одну задачу, нужно за линейное время находить для массива A(N) L[i] — количество подряд идущих чисел до i-го которые больше или равны A[i]. Автор толком не показывает как это сделать, но говорит что стек поможет. Я думал-думал, ничего не выходит придумать. Помогите пожалуйста, объясните как же за линию такой массив насчитать и реально ли это вообще.

Пример

A = {3 1 2 4 5 3 4}

L = {0 1 0 0 0 2 0}

Для тех кто не очень возможно понял суть задачи — для каждого i-го числа мы встаем в позицию i-1 и пока это число >= a[i] то прибавляем 1 в L[i](но это за квадрат решение, а нам линия нужна).

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru1 Русский moskalenco_a 2016-11-21 04:46:57 780 Первая редакция (опубликовано)