Question

Помогите пж, задача на c++ Вывести маршрут максимальной стоимостиВ левом верхнем углу прямоугольной таблицы размером N×M находится черепашка. В каждой клетке таблицы записано некоторое число. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.Подсчитаем сумму чисел, записанных в клетках, через которую проползла черепашка (включая начальную и конечную клетку). Найдите наибольшее возможное значение этой суммы и маршрут, на котором достигается эта сумма.Входные данныеВ первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идут N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.Выходные данныеПервая строка выходных данных содержит максимальную возможную сумму, вторая — маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N−1 букву D, означающую передвижение вниз и M−1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.ПримерыВвод5 59 9 9 9 93 0 0 0 09 9 9 9 96 6 6 6 89 9 9 9 9Вывод74D D R R R R D D что не так с моим решением?#include #include using namespace std;int main() { int n, m, ez; cin>>n>>m; vector > t(n + 1, vector (m + 1)); vector bestm; for(int i = 1; i < t.size(); ++i) { for(int j = 1; j < t[i].size(); ++j) { cin>>t[i][j]; } } vector > d(n + 1,vector (m + 1)); for(int i = 1; i < t.size(); ++i) { for(int j = 1; j < t[i].size(); ++j) { d[i][j] = max(d[i-1][j],d[i][j-1]) + t[i][j]; ez = d[i][j]; } } cout< = 0; i--) { if (bestm[i] == 0) { cout<<"D "; } else { cout<<"R "; } } return 0;}

Answer 1

Ответ:

#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;

}

Объяснение:

Answer 2

Ваш код содержит несколько проблем, которые мешают корректной работе. Давайте их разберем и предложим исправления.

1. Инициализация векторов: Ваши векторы `t` и `d` инициализируются неправильно. Вы пытаетесь увеличить `n` и `m` до `n+++1` и `m+++1`, что не имеет смысла, так как `n` и `m` уже были введены пользователем и не должны изменяться. Вместо этого, вы должны использовать `n` и `m` для инициализации векторов.

2. Заполнение матрицы `d`: Ваш цикл заполнения матрицы `d` неправильный. Вы должны инициализировать `d[i][j]` как `t[i][j]`, а затем обновлять его как максимум из `d[i-1][j]` и `d[i][j-1]` плюс `t[i][j]`.

3. Определение маршрута: Ваш код неправильно определяет маршрут. Вместо того, чтобы проверять, равно ли `bestm[i]` нулю, вы должны проверять, равно ли `d[i][j]` максимальному значению в строке `i`.

Вот исправленный код:

#include 
#include 
#include 
using namespace std;

int main() {
   int n, m;
   cin >> n >> m;
   vector> t(n+1, vector(m+1));
   vector> d(n+1, vector(m+1));
   vector bestm(n+1);
   int maxSum = 0;

for(int i = 1; i <= n; ++i) {
       for(int j = 1; j <= m; ++j) {
           cin >> t[i][j];
           d[i][j] = t[i][j];
       }
   }

for(int i = 1; i <= n; ++i) {
       for(int j = 1; j <= m; ++j) {
           if(i > 1) d[i][j] = max(d[i][j], d[i-1][j] + t[i][j]);
           if(j > 1) d[i][j] = max(d[i][j], d[i][j-1] + t[i][j]);
       }
   }

int i = n, j = m;
   while(i > 1 || j > 1) {
       if(i > 1 && (j == 1 || d[i-1][j] >= d[i][j-1])) {
           bestm[i] = 'D';
           i--;
       } else {
           bestm[i] = 'R';
           j--;
       }
   }

cout << d[n][m] << endl;
   for(int i = 1; i <= n; ++i) {
       cout << bestm[i];
   }

return 0;
}

Этот код сначала считывает размеры таблицы и ее содержимое. Затем он инициализирует матрицу `d` таким же образом, как и матрицу `t`, но обновляет каждый элемент `d[i][j]` как максимум из `d[i-1][j]` и `d[i][j-1]` плюс `t[i][j]`. После этого он определяет маршрут, начиная с правого нижнего угла и двигаясь вверх и влево, пока не достигнет верхнего левого угла. Наконец, он выводит максимальную сумму и маршрут.