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

Найти наибольшую сумму костей домино игрока - C++

Восстановить пароль Регистрация
 
SkRiD
0 / 0 / 0
Регистрация: 06.01.2016
Сообщений: 18
04.04.2016, 18:24     Найти наибольшую сумму костей домино игрока #1
У игрока есть k костей домино - прямоугольников 2x1. Он кладет их на доску так, чтобы не возникало наложений, и его выигрыш вычисляется как сумма произведений чисел, накрытых каждой из костей домино.

Например, существует два способа положить две кости домино на доску размера 2x2.
Код
1 4
3 2
Для доски в лучшем случае сумма составляет 1x3 + 4x2 = 11. Если игрок выберет другой способ , то сумма составит 1x4 + 3x2 = 10, что меньше чем 11.

Домино
По заданному расположению чисел на доске и количеству костей домино, которыми располагает игрок, найдите наибольшую сумму, которую он может получить.

Входные данные:

Первая строка входного файла INPUT.TXT содержит целые числа m, n (размерность доски) и k (1 ≤ m ≤ 16, 1 ≤ n ≤ 100, 1 ≤ k ≤ 200). Следующие m строк содержат по n целых чисел каждая и описывают доску. Числа, записанные на доске, неотрицательны и по величине не превосходят 1000. Гарантируется, что существует хотя бы один способ разместить все кости домино на доске.

Выходные данные:

В выходной файл OUTPUT.TXT выведите одно целое число - наибольшую сумму, которую может получить игрок.

Добавлено через 19 часов 4 минуты
Здесь похожий алгоритм http://e-maxx.ru/algo/min_cost_flow, но не знаю как это реализовать
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.04.2016, 18:24     Найти наибольшую сумму костей домино игрока
Посмотрите здесь:

Найти наибольшую сумму чисел ряда, не превышающую заданное число k. C++
Найти наибольшую сумму цифр подпоследовательностей, ограниченных отрицательными числами C++
C++ Двумерный массив. Найти подмассив, имеющий наибольшую сумму элементов
C++ Найти наибольшую по величине сумму двух соседних элементов массива
Определить, соответствует ли последовательность чисел ряду костей домино C++
Найти наибольшую сумму N последовательных чисел в массиве C++
C++ Построить алгоритм выкладывания костей домино так, чтобы в конце цепочки "на руках" осталось максимум очков.
Найти наибольшую сумму цифр во введенных числах C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SkRiD
0 / 0 / 0
Регистрация: 06.01.2016
Сообщений: 18
06.04.2016, 00:54  [ТС]     Найти наибольшую сумму костей домино игрока #2
Актуально
Yandex
Объявления
06.04.2016, 00:54     Найти наибольшую сумму костей домино игрока
Ответ Создать тему
Опции темы

Текущее время: 13:16. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru