Форум » Обработка числовых последовательностей » №5267 (27.110) другое решение » Ответить
№5267 (27.110) другое решение
beep: Здравствуйте! Решение не такое запутанное, как в "27-110_99ballov.py" и интуитивнее, чем ДП в целом, как мне кажется. [pre2] n = None k = None buff = [] with open("27-110b.txt") as f: n, k = map(int, f.readline().split()) buff.append((k, 0)) for i, x in enumerate(f): a, b = list(map(int, x.split())) buffT = [] for case in buff: buffT.append(case) buffT.append((k, case[1] + b)) if case[0] > 0: buffT.append((case[0] - 1, case[1] + a)) buff = [] buffT.sort(key=lambda x: (-x[1], -x[0])) border = None for case in buffT: if not border or case[0] > border: buff.append(case) border = case[0] buff.sort(key=lambda x: (-x[1], x[0])) print(buff[0][1]) [/pre2] И бонусом ДП без лишних больших массивов, дополнительных итераций и с поточной обработкой (вдруг пригодится кому): [pre2] n = None k = None res = [] with open("27-110b.txt") as f: n, k = map(int, f.readline().split()) res = [[0] * (k + 1) for i in range(2)] for i, x in enumerate(f): a, b = list(map(int, x.split())) for j in range(k + 1): res[1][j] = max(res[0][j], a + res[0][j - 1] if j else b + max(res[0])) res[0], res[1] = res[1], res[0] print(max(res[0])) [/pre2]
Ответов - 1
beep: ап
полная версия страницы