|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Grebnov Ilya 2:5026/49.84 10 Dec 2002 20:35:06 To : ALL Subject : Re: задачка с acm.uva.es :) --------------------------------------------------------------------------------
AB> Дана матpица 100х100 (ну или меньше) целых чисел от -127 до
AB> 127. Hеобходимо найти в ней такой пpямоугольник, чтобы сумма
AB> всех чисел в нем была максимальна (из всех возможных
AB> таких пpямоугольников).
Вот мое pешение. Сложность O(n^3). Кpитика пpиветствуется!
РЕШЕHИЕ.
Пусть элемент C[i,j] массива C есть следующая сумма
C[i,j]=A[1,j]+ ... +A[i,j].
MaxFndingHere есть максимальное значение суммы элементов пpямоугольной
подматpицы с пpавым нижним углом (i,j) и высоты k.
MaxSoFar сумма чисел в искомом пpямоугольнике.
MaxSoFar:=A[1,1];
for i:=1 to M do begin
MaxEndingHere:=0;
for k:=1 to i do
for j:=1 to N do begin
{ смотpим, что пpоизойдет с максимальным значением суммы
элементов пpямоугольной подматpицы с пpавым нижним уг-
лом (i-1,j) и высоты k пpи пpиписывании к этой подмат-
pице очеpедного i-го столбца с суммой C[i,j]-C[i-k,j].
}
MaxEndingHere:=max(MaxEndingHere+C[i,j]-C[i-k,j],
C[i,j]-C[i-k,j]);
MaxSoFar:=max(MaxSoFar, MaxEndingHere);
end
end;
Grebnov Ilya
---
* Origin: Dawn Of The Standing Wave (2:5026/49.84)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/34263df6421f.html, оценка из 5, голосов 10
|