Статья Автор: Мастикова София

gthe uf.

n, m =map(int, input().split())
dp = [[0]*m for i in range(n)]
a = [[0]*m for i in range(n)]
for i in range(n):
    mg = list(map(int, input().split()))
    for j in range(m):
        a[i][j]=mg[j]

dp[0][0]=a[0][0]


flag = True
for i in range(0, m):
    dp[0][i]=dp[0][i-1]+a[0][i]
        
for i in range(0, n):
    dp[i][0] = dp[i-1][0]+a[i][0]
        
        
for i in range(1, n):
    for j in range(1, m):
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])+a[i][j]
print(dp[n-1][m-1])

i = n - 1
j = m - 1
ans = ''
while i > 0 or j > 0:
        if i == 0:
            ans += 'R'
            j-=1
        elif j == 0:
            ans += 'D'
            i -= 1            
        elif (dp[i][j-1] > dp[i-1][j]):
            ans += 'R'
            j-=1
        else:
            ans += 'D'
            i -= 1
print(ans[::-1])

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать