Участник:Penkin.D.A./Chase and Dungeons

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.codechef.com/problems/CHAND

Решаем задачу динамически. Заполняем массив платформ 1 (считаем их безопасными). После этого считываем небезопасные платформы и отмечаем их в массиве 0. Затем, для того чтобы сделать платформу безопасной, мы выбираем минимальный по стоимости вариант исходя из стоимости заклинания и стоимости платформы с которой мы можем сделать ее безопасной.

def Solve():
    m,n=map(int,input().split())
    a = (n+1)*[1]
    b = list(map(int, input().split()))
    for i in range(m):
        a[b[i]] = 0
    cost = list(map(int, input().split()))
    diff = [0, 6, 13, 29]
    dp = (n+1)*[0]
    temp = 0
    for i in range(1, n+1):
        if (a[i] == 1):
            dp[i] = dp[i-1]
            continue
        dp[i] = dp[i-1]+cost[0]
        for j in range(4):
            dp[i] = min(dp[i], dp[max(temp, i-diff[j]-1)]+cost[j])
    print(dp[n])
 
t = int(input())
while t > 0:
    Solve()
    t -= 1