Помоги плез с задачей, чет никакой алгоритм не лезет в голову
B
Динамика
Интересная задача.
1. Если подумать логически, то для каждого перекрестка ты можешь посчитать некий вес, который будет являться суммой окружающих его домов. Получаем матрицу Lx2
2. Далее обрабатываем коллизии. Понимаем, что эффект воздействия магазина на севере и юге одинаковый и приводим матрицу Lx2 к массиву Lх1 каждое значение в котором будет являться наибольшим из этих двух.
3. Поскольку данный массив может включать в себя нулевые или отрицательные значения, которые не оказывают влияния или уменьшают максимальную сумму, то мы можем выделить из основного массива N-ое массивов разделителями между которыми будут являться таковые значения.
4. Далее для каждого массива найдем максимальную сумму. Сделать это можно например вызвав рекурсивный метод. Данный метод на вход получит массив и текущее значение итератора, а вернет максимальную сумму. Так как максимальная сумма зависит от всех выбранных элементов в последовательности, то выглядеть оно будет примерно так:
Max_sum(array, i){
var sum_with_value = array + Max_sum(array, i + 2);
var sum_with_out_value = array[i+1] + Max_sum(array, i + 3);
if(sum_with_value > sum_with_out_value){
return sum_with_value;
} else{
return sum_with_out_value;
}
}
5. После того как по каждому массиву нашли максимальную сумму, суммируем их и получаем итоговую максимальную сумму.
Данное решение скорее всего не идеальное, но мне похуй. Я в танке
