[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Олимпиадное программирование ->Обсуждение Sphere-задач
Author Message
Vladimir Minyaylov

Topics: 9
Messages: 30

My Profile
По просьбе Генадия Короткевича выкладываю разбор.
1. Уменьшим числа в обоих последовательностях на 1. Теперь стоимость (S1-K1)*(S2-K2) меняется на S1*S2.
2. Очевидно ДП для O(N^4). Далее будем сводить его к O(N^2).
3. Сделаем матрицу Cij, где Cij=Ai*Bi. Далее ответ представляет N прямоугольников. Описывать прямоугольник будем четыремя числами Xi,1 Yi,1(левый верхний угол) Xi,2 Yi,2 (правый нижний угол). У них будут слудующие свойства:
X1,1=1 Y1,1=1
Xi+1,1 = Xi,2 + 1
Yi+1,1 = Yi,2 + 1
Xn,2 = кол-во элементво в A
Yn,2 = кол-во элементво в B
Стоимость - это общая сумма всех чисел в прямоугольнике.
По сути каждый прямлугольник раскрывает выражение вида:
(сумма некоторых элементов из A)*(сумма некоторых элементов из B)
4. Теперь предположим, что некотрый прямоугольник имеет длину и ширину больше 1. Очевидно, что его можно заменить на некоторое кол-во других прямоугольников с длиной(или шириной) равной 1. При этой замене ответ не ухудшается(все Cij неотрицательные по условию). Основываясь на этом очевидно решение за O(N^3).
5. Для решения за O(N^2) будем использовать следующее ДП:
Fij = min(Fi-1,j , Fi,j-1 , Fi-1,j-1) + Cij
Это конечный вариант и сложность составляет O(N^2).
Gennadiy Korotkevich

Topics: 6
Messages: 37

My Profile
Спасибо!
______________________
Nothing is impossible; impossible itself says: "I m possible"...
 
Forum Index ->Олимпиадное программирование ->Обсуждение Sphere-задач
Time:0,078