#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n(0),m(0);
cin >> n >> m;
int matrix[n][m];
char arr[n][m];
arr[0][0] = '0';
for(int i = 0;i<n;++i){
for(int j = 0;j<m;++j){
cin >> matrix[i][j];
if(!i && !j)continue;
if(!i){
matrix[i][j] += matrix[i][j-1];
arr[i][j] = 'R';
}
if(!j){
matrix[i][j] += matrix[i-1][j];
arr[i][j] = 'D';
}
if(i && j){
matrix[i][j] += max(matrix[i-1][j],matrix[i][j-1]);
if(max(matrix[i-1][j],matrix[i][j-1]) == matrix[i-1][j])arr[i][j] = 'D';
else arr[i][j] = 'R';
}
}
}
cout << matrix[n-1][m-1];
cout << "\n";
string s;
for(int i = n-1;;){
for(int j = m-1;;){
if(arr[i][j] == '0'){
reverse(s.begin(),s.end());
s.erase(0,1);
cout << s << endl;
return 0;
}
s.push_back(arr[i][j]);
s.push_back(' ');
if(arr[i][j] == 'R'){
j -= 1;
continue;
}
if(arr[i][j] == 'D'){
i -= 1;
continue;
}
}
}
cout << endl;
return 0;
}
global n,m,matrix,pathmatrix
def rec(x, y):
try:
return pathmatrix[x,y]
except:
if x > 0:
left = rec(x - 1, y)
else:
left = (-1,[])
if y > 0:
up = rec(x, y - 1)
else:
up = (-1,[])
maxdist = max(left[0], up[0]) + matrix[x][y]
if left[0] > up[0]:
path = pathmatrix[x - 1,y][1].copy()
path.append('D')
else:
path = pathmatrix[x,y - 1][1].copy()
path.append('R')
pathmatrix[x,y] = (maxdist,path)
return pathmatrix[x,y]
n,m = [int(i) for i in input().split()]
matrix = [[int(i) for i in input().split()] for j in range(n)]
pathmatrix = {(0,0) : (matrix[0][0], [])}
res = rec(n-1,m-1)
print(res[0])
print(' '.join(res[1]))
global n,m,matrix,pathmatrix
def rec(x, y):
try:
return pathmatrix[x,y]
except:
if x > 0:
left = rec(x - 1, y)
else:
left = (-1,[])
if y > 0:
up = rec(x, y - 1)
else:
up = (-1,[])
maxdist = max(left[0], up[0]) + matrix[x][y]
if left[0] > up[0]:
path = pathmatrix[x - 1,y][1].copy()
path.append('D')
else:
path = pathmatrix[x,y - 1][1].copy()
path.append('R')
pathmatrix[x,y] = (maxdist,path)
return pathmatrix[x,y]
n,m = [int(i) for i in input().split()]
matrix = [[int(i) for i in input().split()] for j in range(n)]
pathmatrix = {(0,0) : (matrix[0][0], [])}
res = rec(n-1,m-1)
print(res[0])
print(' '.join(res[1]))
Объяснение: