d = [0] + [-1e9] * 4000 - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: General Coding Help (https://python-forum.io/forum-8.html) +--- Thread: d = [0] + [-1e9] * 4000 (/thread-23120.html) |
d = [0] + [-1e9] * 4000 - SakshiSingh - Dec-12-2019 Problem: Cut Ribbon Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions: After the cutting each ribbon piece should have length a, b or c. After the cutting the number of ribbon pieces should be maximum. Help Polycarpus and find the number of ribbon pieces after the required cutting. Input The first line contains four space-separated integers n, a, b and c (1 ≤ n, a, b, c ≤ 4000) — the length of the original ribbon and the acceptable lengths of the ribbon pieces after the cutting, correspondingly. The numbers a, b and c can coincide. Output Print a single number — the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists. Examples input 5 5 3 2 output 2 input 7 5 5 2 output 2 Note In the first example Polycarpus can cut the ribbon in such way: the first piece has length 2, the second piece has length 3. In the second example Polycarpus can cut the ribbon in such way: the first piece has length 5, the second piece has length 2. I was solving the 189A problem of codeforces and I came across this solution. I am not able to understand the expression: d = [0] + [-1e9] * 4000 in the 4th line of code Can anyone please explain me the use of 'd = [0] + [-1e9] * 4000' in the below code. n, a, b, c = map(int, input().split()) d = [0] + [-1e9] * 4000 for i in range(1, n + 1): d[i] = max(d[i - a], d[i - b], d[i - c]) + 1 print(d[n])Code Link: https://codeforces.com/problemset/problem/189/A RE: d = [0] + [-1e9] * 4000 - Gribouillis - Dec-12-2019 At the beginning of the procedure, the indexes i-a, i-b, i-c can be negative, which means that python is going to take values at the end of the array, because for example d[-4] is the 4th value from the right. Initializing the array to a large negative value in each cell is intended as giving the cell a "negative infinite" value for the max algorithm. Atevery step, an increment of 1 is added, so the number is chosen large enough so that -1e9 + 4000 < 0
RE: d = [0] + [-1e9] * 4000 - SakshiSingh - Dec-12-2019 Thank you. RE: d = [0] + [-1e9] * 4000 - Gribouillis - Dec-12-2019 Another perhaps more elegant choice would have been float("-infinity")
|