Список вопросов
Как мне добавить решение на задач ?
14th February, 15:14
779
0
Что dsu(i) значит в коде "катание на коньках"
8th February, 18:16
177
1
Страна замов. Напишите программу на Python
10th December, 18:14
571
2
На листе клетчатой бумаги рисуют выпуклый 100-угольник с вершинами в узлах сетки. Какое наибольшее число диагоналей этого 100-угольника может идти по линиям сетки?
7th November, 15:29
411
0
Рассмотрим все прямоугольники, длины сторон которых выражены целым числом метров, и периметр которых (в метрах) численно равняется площади (в метрах квадратных). Найдите суммарную площадь всех таких, разных по размеру сторон, прямоугольников.Прямоугольники, отличающиеся порядком сторон, например, 10 * 20 и 20 * 10 считаем одинаковыми.
7th October, 20:57
864
0
Кто и за сколько может написать программу управления курсором?
2nd October, 23:48
582
3
Как авторизоваться на novafilm.tv при помощи cURL?
2nd October, 23:33
466
3
Верстка, position:relative создает пустое место
2nd October, 23:31
402
2
Что улучшить в переводе Apache Public License?
2nd October, 23:29
404
1
Формирование кода видео Вконтакте
2nd October, 23:23
507
3
IPad2 с 3G из Штатов?
2nd October, 23:18
456
5
А будет ли tcpdump видеть ack flood?
2nd October, 23:14
374
2
Альфа банк и странное смс мошенничество?
2nd October, 23:05
757
6
Софт для "ремонта" поврежденного h264 видео?
2nd October, 22:55
380
3
Scrapy — Python
2nd October, 22:54
389
4
Помощь с доставкой из США?
2nd October, 22:47
427
3
Создание stop-motion ролика
2nd October, 22:41
463
5
Решение задачи Минимальный путь в таблице с Acmp
Без пояснения   Просмотров: 266
В прямоугольной таблице N×M (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).
Код
#include using namespace std; int main() { int m,n; cin >> m >> n; int a[m][n]; int b[m][n]; for(int i = 0; i < m; ++i) for(int j = 0; j < n; ++j) cin >> a[i][j]; if(m == 1 && n == 1){ cout << a[0][0]; return 0; } for(int i = 0; i < m; ++i) for(int j = 0; j < n; ++j) b[i][j] = 0; b[m - 1][n - 1] = a[m - 1][n - 1]; for(int i = m - 2; i >= 0; --i) b[i][n - 1] = b[i + 1][n - 1] + a[i][n - 1]; for(int i = n - 2; i >= 0; --i) b[m - 1][i] = b[m - 1][i + 1] + a[m - 1][i]; for(int i = m - 2; i >= 0; --i){ for(int j = n - 2; j >= 0; --j){ b[i][j] = min(b[i + 1][j], b[i][j + 1]) + a[i][j]; } } int i = 0, j = 0,s = a[0][0]; while(i != m - 1 && j != n - 1){ if(b[i + 1][j] > b[i][j + 1]) ++j; else ++i; s+=a[i][j]; } if(i == m - 1 && j != n - 1) for(int h = j + 1; h < n - 1; ++h) s+=a[i][h]; if(j == n - 1 && i != m - 1) for(int h = i + 1; h < m - 1; ++h) s+=a[h][j]; s+=a[m - 1][n - 1]; cout << s; return 0; }
 
 
 
 
 
Автор: Администратор
