problem.txt (1335B)
1 Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions: 2 3 After the cutting each ribbon piece should have length a, b or c. 4 After the cutting the number of ribbon pieces should be maximum. 5 6 Help Polycarpus and find the number of ribbon pieces after the required cutting. 7 8 --- 9 10 - length == n 11 - conditions: 12 - after cutting ribbons pieces should have length a,b,c 13 - after cutting the number of ribbon pieces should be maximum 14 - so basically we want as many of the shortest and one of the rest perhaps 15 16 --- 17 18 n,a,b,c <= 4000 19 20 5 5 3 2 21 22 n = 5 23 a = 5 24 b = 3 25 c = 2 26 27 we can either not cut, or we can cut at 3 to get b and c lengths (2) 28 29 30 --- 31 32 n=7 33 a=5 34 b=5 35 c=2 36 37 7 5 5 2 38 39 5 + 2 = 7 40 41 we can cut one segment with a/b length and one with c's length: 42 43 ans: 2 44 45 --- 46 47 - idea: 48 - given that n <= 4000, it might be possible to just try all combinations at each step 49 - there are 4000-1 possible locations, and from each of these there are only at most 3 cuts of consequence we can make 50 - size a,b,c 51 - at a certain location, we only care about further cuts from that point on that fill the space up to the given location 52 - dp problem 53 54 --- 55 56 - dp formulation: 57 - state := (index) 58 - transition := as possible, cut size a,b,c