Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Высший пилотаж, или как уменьшить штраф - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Подсчитать количество локальных минимумов заданной матрицы http://www.cyberforum.ru/cpp-beginners/thread66928.html
Приветик всем!!! Мне тут подружка принесла задание с котрым я не могу справится,надо написать прогрмку на С++ Помогите пожайлуста!!!Расцелую всех:) Вот само задание: В ходе выполнения...
C++ подсчет символов Помогите пожалуйста решить задачку. я полный нуб в с++ но очень нужно решение. Написать программу, которая считывает текстовый файл и выводит на экран какие буквы встречаются в этом файле, а также... http://www.cyberforum.ru/cpp-beginners/thread66918.html
Динамический двумерный массив C++
Кому не трудно, помогите. Нужно написать двумерный массив любой размерности, и посчитать сумму элементов в каждой диагонали массива. Желательно, чтобы размерность была 4х4.
C++ Класс круговая очередь Помoгите плз
У меня задание создать круговую очередь( я тока начал изучать классы так что многово не понимаю ) помогите исправить ошибки плз #include <iostream> using namespace std; class queue{ int...
C++ Построить таблицу значений для функции на отрезке http://www.cyberforum.ru/cpp-beginners/thread66886.html
1.Составить программу вычисления функции и определить характер её зависимости от значений исходных данных. с=|(n+z^5)/(3+z)| где z=n+ctg(n+1)/sin(n+1) 2.Составить согласно варианту программу на...
C++ Сортировка двумерного массива... Дано: одномерный массив А заполненный случайными числами одномерный массив В заполненный случайными числами двумерный массив С размером АхВ Он заполняется суммой ячеек массива А + ячейки... подробнее

Показать сообщение отдельно
odip
Эксперт С++
7158 / 3220 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
24.11.2009, 16:56
Минимальный штраф

Задана матрица натуральных чисел A(n, m), где n – количество строк, m – количество столбцов. За каждый проход через клетку (i, j) взимается штраф A(i, j). Необходимо минимизировать штраф и пройти из какой-либо клетки первой строки (приложение должно выбрать оптимальную стартовую ячейку) в любую клетку последней n-ой строки. При этом из текущей клетки можно перейти в любую из 3-х соседних ячеек в пределах матрицы, стоящих в стpоке с номеpом на 1-цу большем (можно двигаться вниз, вниз по диагонали влево, вниз по диагонали вправо).
Известно, что 1 <= n <= 1000, 1<= m <= 1000, программа должна работать правильно при любых допустимых значениях n и m, даже если они равны 1.
Ввод из файла “input.txt”. В первой строке через пробел содержатся значения n и m (размеры матрицы), в последующих строках – сама матрица штрафов. Вывод в файл “output.txt”. В первой строке выходного файла содержится суммарный штраф по пути следования, во второй – последовательность набранных штрафов.

Примеры входных данных
input.txt
Код
4	5
3	2	8	6	4
4	7	12	9	1
55	8	3	2	8
20	7	4	9	1
input.txt
Код
3	1
3
4
1
Соответствующие выходные данные
output.txt
Код
8
4	1	2	1
output.txt
Код
8
3	4	1
Добавлено через 1 минуту
Типичная задача на динамическое программирование.
Такую задачу уже решали на форуме.
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru