Задача к ЕГЭ по информатике на тему «Стандартные задачи» №2

Просмотров 6 Комментарии 0

В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс $B$ зависит от процесса $A$ , если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$ . В этом случае процессы могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса $(ID )$ , во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем « $;$ » $ID$ процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение $0$ .

Типовой пример организации данных в файле:

|----------------|-------------------------------------|--------------------| |ID--про-цесса-B-|В-рем-я-вып-олнен-ия-проц-есса B-(м-с)|ID-п-роцесса(ов)A--| | 1 | 4 | 0 | |-------2--------|------------------3------------------|---------0----------| |----------------|-------------------------------------|--------------------| |-------3--------|------------------1------------------|--------1;2---------| --------4---------------------------7----------------------------3----------|

Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

from functools import lru_cache
n = int(input())
time = [0 for i in range(n + 1)]
depends = [[] for i in range(n + 1)]

@lru_cache(None)
def lazy_dp(k):
    if depends[k][0] == 0:
        return time[k]
    else:
        m = -1
        for i in depends[k]:
            m = max(m, lazy_dp(i))
    return m + time[k]

for i in range(1, n + 1):
    a = list(map(int, input().split()))
    time[i] = a[0]
    del a[0]
    depends[i] = a.copy()
ans = -1
for i in range(1, n + 1):
    ans = max(ans, lazy_dp(i))
print(ans)

Ответ: 23