Question

Башня Петя в очередной раз купил себе набор из кубиков. На этот раз он выстроил из них настоящую крепость — последовательность из N столбиков, высота каждого столбика составляет A i кубиков. Вскоре ему стало интересно, насколько его крепость защищена от жуликов и воров. Для этого он ввел понятие башни. Башней называется любая последовательность из K столбиков подряд (где K — любимое число Пети). Защищенность башни определяется как суммарная высота всех столбиков этой башни (чем она больше, тем громаднее и ужаснее она кажется), умноженная на минимум высоты столбиков башни (т.к. враги, очевидно, будут пытаться проникнуть через самое слабое место башни). Неприступность крепости определяется как сумма защищенностей каждой из башен. Петя решил как можно скорее посчитать, какова же неприступность его крепости. Однако вскоре он понял, что недостаточно знать высоту каждого из столбиков. В зависимости от того, как сгруппировать столбики в башни, получится разный результат. В различных вариантах группировки часть столбиков могут не принадлежать ни одной из башен. Разумеется, Петя выберет то разбиение на башни, при котором неприступность будет максимальна. Петя успешно справился со своей задачей, но теперь Правительство Флатландии решило защитить свой горный курорт. Правительство уже построило крепость из кубиков (просто кубики были побольше). Теперь вы должны помочь Правительству посчитать неприступность этой крепости. Единственная трудность состоит в том, что у Правительства было очень много денег, и поэтому крепость была построена очень длинная. Входные данные В первой строке содержатся число N — количество столбиков в крепости и число K — любимое число Пети (1≤≤≤100000 1 ≤ K ≤ N ≤ 100 000 ). Далее в следующей строке содержатся N целых чисел, обозначающих A i (1≤≤106) ( 1 ≤ A i ≤ 10 6 ) . Выходные данные В первой строке выведите число Q — количество башен в оптимальном разбиении. Далее выведите Q чисел — номера первых столбиков каждой башни. Примеры Ввод Вывод 8 3 1 2 3 4 1 6 7 8 2 2 6

Answer 1

Ответ:

from collections import deque

 

n, k = map(int, input().split())

x, d, ssum = list(map(int, input().split())), deque(), 0

b = [(0,0) for i in range(n)]

for i in range(n):

   ssum += x[i]

   if i >= k :

       ssum -= x[i - k]

       if d[0] == i - k :

           d.popleft()

   while len(d) and x[d[-1]] >= x[i]:

       d.pop()

   d.append(i)

   if i >= k - 1:

       nb = (b[i-k][0] + x[d[0]] * ssum, i-k+2)

       b[i] = max(b[i-1], nb, key=lambda x: x[0])

i = n - 1

d = deque()

j = b[-1][1]

d.appendleft(j)

while i !=0:

   i -= 1

   j1 = b[i][1]

   if j-k>=j1 and j1 > 0 :

       d.appendleft(j1)

       j = j1

print(str(len(d)))

print(" ".join(map(str, d)))

Answer 2

Данная задача связана с оптимальным разбиением последовательности столбиков на башни и подсчетом их неприступности. Давайте разберемся, как это сделать.

Алгоритм решения:

1. Входные данные содержат число N - количество столбиков в крепости, и число K - любимое число Пети.
2. Читаем последовательность высот столбиков Ai.
3. Создаем массив tower_strength размером N и заполняем его нулями. В этом массиве будем хранить неприступность каждой башни.
4. Создаем массив dp размером N + 1 и заполняем его нулями. В этом массиве будем хранить оптимальные значения неприступностей для каждой позиции столбика.
5. Создаем массив prev размером N + 1 и заполняем его нулями. В этом массиве будем хранить предыдущий столбик для каждой позиции столбика.
6. Проходимся по каждой позиции i от 1 до N:
   • Инициализируем переменную max_strength = 0 и max_prev = 0.
   • Проходимся по каждой позиции j от max(i - K, 0) до i - 1:
     • Если значение dp[j] больше max_strength, обновляем max_strength = dp[j] и max_prev = j.
   • Вычисляем неприступность текущего столбика как (Ai * (i - max_prev)).
   • Если неприступность текущего столбика больше значения dp[i], обновляем dp[i] = неприступность текущего столбика и prev[i] = max_prev.
7. Находим позицию i_max, где dp[i_max] максимально.
8. Строим последовательность башен, начиная с позиции i_max, используя значения prev[i] для каждого столбика.
9. Выводим количество башен Q, которое равно длине последовательности башен, и номера первых столбиков каждой башни.

Пример реализации на языке Python:

pythonCopy code
def calculate_tower_defensibility(N, K, heights):
    tower_strength = [0] * N
    dp = [0] * (N + 1)
    prev = [0] * (N + 1)

    for i in range(1, N + 1):
        max_strength = 0
        max_prev = 0

        for j in range(max(i - K, 0), i):
            if dp[j] > max_strength:
                max_strength = dp[j]
                max_prev = j

        tower_strength[i - 1] = heights[i - 1] * (i - max_prev)

        if tower_strength[i - 1] > dp[i]:
            dp[i] = tower_strength[i - 1]
            prev[i] = max_prev

    i_max = dp.index(max(dp))
    towers = []