|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexey Burdin 2:5012/32.768 08 Dec 2002 00:42:57
To : All
Subject : задачка с acm.uva.es :)
--------------------------------------------------------------------------------
> from: /Unknown/
Как после вчерашнего, All ?
Дана матрица 100х100 (ну или меньше) целых чисел от -127 до 127.
Hеобходимо найти в ней такой прямоугольник, чтобы сумма всех чисел
в нем была максимальна (из всех возможных таких прямоугольников).
Hа ум (?) сразу приходит полный перебор: 1<=x1,y1<=100 , x1<=x2<=100,
y1<=y2<=100, s=sum a[y,x] x1<=x<=x2, y1<=y<=y2.
Для матрицы 100х100 считал на Celeron 466 аж 15 минут :)
Хотелось бы что-нибудь более оптимальное, но влезающее в досовые 400к :),
желательно чтобы работало на "раз-два-три".
Всего хорошего. Alexey.
... А что подyмал кpолик, никто не yзнал,
--- потомy что кpолик был очень воспитанный.
* Origin: I do... hope you have a clue (2:5012/32.768)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
