Задача на сириусе

Question

Задача на сириусе

Наталья Викторовна Ученик (228), закрыт 1 год назад

Cамый дешёвый путь В каждой клетке прямоугольной таблицы N×M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути). Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол.

Answer 1

максимально баянистая двумерная динамика:

 #include 
#include 
 

using namespace std;
 

int main() {
    int n, m;
    cin >> n >> m;
    vector> a(n, vector(m)), d(n, vector(m, INT_MAX));
    for (auto &i: a)
        for (auto &j: i)
            cin >> j;
    d[0][0] = a[0][0];
    for (int i = 1; i < m; i++) d[0][i] = d[0][i - 1] + a[0][i];
    for (int i = 1; i < n; i++) d[i][0] = d[i - 1][0] + a[i][0];
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++)
            d[i][j] = min(d[i - 1][j], d[i][j - 1]) + a[i][j];
    cout << d[n - 1][m - 1];
}

Answer 2

kill blod 2007-2023 RIP Просветленный (23286) 1 год назад

с помощью exel это можно решить