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

Выделить в матрице квадрат, в котором количество разных чисел не меньше K - C++

Восстановить пароль Регистрация
 
Session
Сообщений: n/a
11.03.2011, 16:40     Выделить в матрице квадрат, в котором количество разных чисел не меньше K #1
Помогите решить вот такую задачу:
Дано N - количество рядов, M - количество столбцов, K - минимальное количество разных чисел на квадрат.
Есть участок размером N*M, содержащий разные числа от 1 до 1000000000. Нам нужно из этого участка выделить квадрат(!), в котором количество разных чисел не меньше K. Причем этот квадрат должен быть минимальной площади. В общем, вывести требуется только правильную площадь
Пределы: 1 ≤ N, M ≤ 300, 1 ≤ K ≤ 90000
Пример:
Вход: (выделил квадрат)
5 5 3
1 2 2 2 4
1 2 2 2 2
1|1 2 2|2
2|1 2 2|2
1|1 2 3|3
Выход:
9
Наведите на решение, ничего кроме брутфорса в голову не лезет.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2011, 16:40     Выделить в матрице квадрат, в котором количество разных чисел не меньше K
Посмотрите здесь:

C++ Дано целое число N и набор из N целых чисел. Определить номера тех чисел наборе, которые меньше своего правого соседа, и количество К таких чисел.
C++ находит такое, в котором наибольшее количество разных букв.
Вычислить количество чисел, квадрат которых меньше 10 C++
C++ Массив: Удалить строку, в котором есть слово, имеющее наибольшее количество разных букв.
C++ Файлы. С файла нужно удалить слово, в котором самое большое количество РАЗНЫХ букв
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
slice
32 / 75 / 4
Регистрация: 04.11.2010
Сообщений: 249
11.03.2011, 16:57     Выделить в матрице квадрат, в котором количество разных чисел не меньше K #2
гугли: применение динамического программирования для задачи вариационного размещения
Session
Сообщений: n/a
11.03.2011, 18:51     Выделить в матрице квадрат, в котором количество разных чисел не меньше K #3
Почитал, так и не понял, как это относится к моей задаче... Можете поточнее сказать, а не посылать в поиск?
eXceibot
Сообщений: n/a
17.03.2011, 22:17     Выделить в матрице квадрат, в котором количество разных чисел не меньше K #4
Задача предложена на заочной олимпиаде школьников Томского политехнического университета. Просьба ко всем участникам форума - не предлагать решений этой задачи. Пусть сам думает.
Yandex
Объявления
17.03.2011, 22:17     Выделить в матрице квадрат, в котором количество разных чисел не меньше K
Ответ Создать тему
Опции темы

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