Форум » Динамическое программирование » Генератор ЕГЭ, задача 2368 » Ответить
Генератор ЕГЭ, задача 2368
SergeyK: Здравствуйте. Задача 2368 В ответе: 1276 719 И в Excel и на языке программирования получается: 1276 416
Ответов - 5
Поляков: Рассказывайте, как получилось 416.
SergeyK: [pre2] dp = [] def create_dp(n, m): global dp dp = [[0] * m for _ in range(n)] d = [] for s in open("18.txt"): d.append([0] + [int(i) for i in s.split()]) #print(d) m = len(d[0]) d.append([0] * m) n = len(d) create_dp(n, m) #print(dp) for i in range(n - 2, -1, -1): for j in range(1, m): dp[ i ][j] = max(dp[ i ][j-1], dp[i+1][j]) + d[ i ][j] print(dp[0][-1]) create_dp(n, m) for i in range(n - 2, -1, -1): for j in range(1, m): dp[ i ][j] = min(dp[ i ][j-1], dp[i+1][j]) + d[ i ][j] print(dp[0][-1]) [/pre2] 63 78 58 93 49 83 92 3 51 57 10 1 42 24 55 59 66 48 76 79 25 29 87 76 99 63 32 22 87 48 88 40 65 9 86 38 56 31 46 95 79 91 77 62 60 73 90 44 41 51 47 39 73 7 68 4 91 32 75 44 59 65 23 87 58 93 64 34 1 64 42 96 69 33 83 8 37 41 37 91 49 27 94 18 89 55 31 97 62 92 25 68 71 13 67 83 37 22 13 8
Поляков: Давайте посмотрим на таблицу Excel. Начали из левой нижней клетки, в которую вписана формула. В ней - 25. Затем прошли вверх. В эту клетку нет другого пути. В ней - 49. Поэтому мы должны получить 25 + 49 = 74.
SergeyK: Да, действительно, просмотрел, спасибо. Хорошая задача. [pre2] dp = [] def create_dp(n, m, ex): global dp x = {"min": 10 ** 4, "max": 0} dp = [[x[ex]] * m for _ in range(n)] dp[n - 2][0] = 0 d = [] for s in open("18.txt"): d.append([0] + [int(i) for i in s.split()]) #print(d) m = len(d[0]) d.append([0] * m) n = len(d) create_dp(n, m, "max") #print(dp) for i in range(n - 2, -1, -1): for j in range(1, m): dp[ i ][j] = max(dp[ i ][j-1], dp[i+1][j]) + d[ i ][j] print(dp[0][-1]) create_dp(n, m, "min") for i in range(n - 2, -1, -1): for j in range(1, m): dp[ i ][j] = min(dp[ i ][j-1], dp[i+1][j]) + d[ i ][j] print(dp[0][-1]) ''' 1276 719 ''' [/pre2]
SergeyK: Даже не знаю, какой вариант проще, если исключить Excel: [pre2] dp = [] def create_dp(n, m): global dp dp = [[0] * m for _ in range(n)] dp[n - 1][0] = d[n - 1][0] for j in range(1,m) : dp[n - 1][j] = d[n - 1][j] + dp[n - 1][j-1] for i in range(n - 2,-1, -1) : dp[0] = d[0] + dp[i + 1][0] d = [] for s in open("18.txt"): d.append([int(i) for i in s.split()]) #print(d) m = len(d[0]) n = len(d) create_dp(n, m) for i in range(n - 2, -1, -1): for j in range(1, m): dp[ i ][j] = max(dp[ i ][j-1], dp[i+1][j]) + d[ i ][j] print(dp[0][-1]) for i in range(n - 2, -1, -1): for j in range(1, m): dp[ i ][j] = min(dp[ i ][j-1], dp[i+1][j]) + d[ i ][j] print(dp[0][-1]) [/pre2]
полная версия страницы