|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Anton Kuznetsov 2:5030/566.13 08 Dec 2002 15:14:00 To : Alexey Burdin Subject : задачка с acm.uva.es :) --------------------------------------------------------------------------------
AB> Дана матрица 100х100 (ну или меньше) целых чисел от -127 до 127.
AB> Hеобходимо найти в ней такой прямоугольник, чтобы сумма всех чисел
AB> в нем была максимальна (из всех возможных таких прямоугольников).
AB>
AB> Hа ум (?) сразу приходит полный перебор: 1<=x1,y1<=100 , x1<=x2<=100,
AB> y1<=y2<=100, s=sum a[y,x] x1<=x<=x2, y1<=y<=y2.
AB> Для матрицы 100х100 считал на Celeron 466 аж 15 минут :)
А как ты считал сумму в каждом прямоугольнике?
Я бы делал примерно то же самое, только динамически.
Т.е для каждой клетки (считая, что она - левый верхний угол) и для всех
возможных длин и ширин :) прямоугольников считал бы эту сумму, а потом выбирал
максимум - вроде так не должно много работать...
До свидания, Alexey!
* Origin: ФТШ - школа наша! (2:5030/566.13)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/39343df32a61.html, оценка из 5, голосов 10
|