vov44k

Untitled

Oct 9th, 2022
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.97 KB | None | 0 0
  1. N, M = map(int, (input().split()))
  2. coinsmap = []
  3. dp = [[float("-inf")] * (M + 1) for i in range(N + 1)]  # Массив стоимостей монет и массив для ДП должны быть разными.
  4. # Для удобства сделал его на 1 больше. Так не надо делать отдельный проверки, чтобы не выйти за границы массива.
  5.  
  6. dp[0][1] = 0  # Начальное состояние
  7. for j in range(N):
  8.     coinsmap.append(list(map(int, (input().split()))))
  9.  
  10. for i in range(1, N + 1):  # Идём от 1 до N включительно
  11.     for j in range(1, M + 1):
  12.         a = dp[i - 1][j]
  13.         b = dp[i][j - 1]
  14.  
  15.         dp[i][j] = coinsmap[i - 1][j - 1] + max(a, b)
  16.  
  17. ans = ""
  18. i, j = N, M
  19. while i - 1 != 0 or j - 1 != 0:
  20.     if dp[i][j - 1] > dp[i - 1][j]:
  21.         j -= 1
  22.         ans += "R"
  23.     else:
  24.         i -= 1
  25.         ans += "D"
  26.  
  27. print(dp[N][M])
  28. print(ans[::-1])
  29.  
Advertisement
Add Comment
Please, Sign In to add comment