|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexey Burdin 2:5012/32.768 09 Dec 2002 03:43:40
To : Anton Kuznetsov
Subject : задачка с acm.uva.es :)
--------------------------------------------------------------------------------
> from: /Unknown/
Как после вчерашнего, Anton ?
14:14 Воскресенье Декабрь 08 2002, Anton Kuznetsov --> Alexey Burdin:
AB>> Дана матрица 100х100 (ну или меньше) целых чисел от -127 до 127.
AB>> Hеобходимо найти в ней такой прямоугольник, чтобы сумма всех чисел
AB>> в нем была максимальна (из всех возможных таких прямоугольников).
AB>> Hа ум (?) сразу приходит полный перебор: 1<=x1,y1<=100 ,
AB>> x1<=x2<=100, y1<=y2<=100, s=sum a[y,x] x1<=x<=x2, y1<=y<=y2.
AB>> Для матрицы 100х100 считал на Celeron 466 аж 15 минут :)
AK> А как ты считал сумму в каждом прямоугольнике?
AK> Я бы делал примерно то же самое, только динамически.
А в чём разница, я не уловил :)
AK> Т.е для каждой клетки (считая, что она - левый верхний угол) и для
AK> всех возможных длин и ширин :) прямоугольников считал бы эту сумму, а
AK> потом выбирал максимум - вроде так не должно много работать...
Однако порядка 100^6 операций извлечения из 2-мерного массива и
суммирования :(
Исходник ушел нетмылом :) А ты проверь. Hапиши и проверь :)
2All: Оптимизацию/другой алгоритм хочу!
Всего хорошего. Alexey.
... А что подyмал кpолик, никто не yзнал,
--- потомy что кpолик был очень воспитанный.
* Origin: No, GWC (2:5012/32.768)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
задачка с acm.uva.es :)