Q4
unknown
python
2 years ago
951 B
5
Indexable
n = int(input()) d = list(map(int, input().split())) t = list(map(int, input().split())) # تعیین فاصله اولیه هر میز تا درب pos = [0] for i in range(1, n): pos.append(pos[i-1] + d[i]) # تعیین هزینه لغزش هر میز slip_cost = [] for i in range(n): cost = 0 for j in range(i, n): if pos[j] - pos[i] > d[i]: cost += abs(pos[j] - pos[i] - d[i]) * t[i] elif pos[j] - pos[i] < d[i]: cost += abs(pos[j] - pos[i] - d[i]) * t[j] slip_cost.append(cost) # تعیین هزینه چسباندن هر میز stick_cost = [abs(t[i]) for i in range(n)] # پیدا کردن کمترین هزینه با استفاده از الگوریتم داینامیک dp = [float('inf')] * (n+1) dp[0] = 0 for i in range(1, n+1): for j in range(i): dp[i] = min(dp[i], dp[j] + sum(slip_cost[j:i]) + sum(stick_cost[j:i])) print(dp[n])
Editor is loading...