Підводний човен#162

Підводний човен (Розбір)

Розберемо форму «човна». Вона складається з трьох частин:

  • корпус — горизонтальна смуга в одному рядку y_1, від стовпця x_1 до x_2 (щонайменше дві клітинки);

  • рубка — вертикальна смуга в стовпці x_3, що йде від рядка корпусу вгору, де x_1 \le x_3 < x_2;

  • хвіст — вертикальна смуга в стовпці x_4, що перетинає рядок корпусу і йде і вгору, і вниз, де x_3 < x_4 \le x_2.

Обидві вертикальні частини можуть вироджуватися в одну клітинку самого корпусу (умови y_1 \le y_2 та y_3 \le y_1 \le y_4 нестрогі).

Зафіксуємо рядок корпусу і порахуємо для кожного стовпця дві допоміжні величини:

  • — найкраща сума суцільної вертикальної смуги строго вище рядка у стовпці ; якщо вона від'ємна, беремо (смугу вигідно залишити порожньою);

  • — те саме для смуги строго нижче рядка .

Обидві рахуються звичайним Кадане по стовпцях і оновлюються за при переході до наступного рядка, тому весь препроцесинг — .

Тепер ідемо по стовпцях зліва направо і ведемо три стани — скільки частин човна вже «зібрано»:

  • S_j — найкраща сума самого корпусу, що закінчується в стовпці :

    S_j = \max(S_{j-1},\, 0) + a_{i,j};
  • P_j — корпус разом з рубкою, де рубка вже поставлена десь у стовпці \le j:

    P_j = \max\bigl(P_{j-1} + a_{i,j},\;\; S_j + \mathrm{up}[j]\bigr);
  • R_j — корпус, рубка і хвіст, де хвіст стоїть у стовпці \le j:

    R_j = \max\bigl(R_{j-1},\;\; P_{j-1} + \mathrm{up}[j] + \mathrm{down}[j]\bigr) + a_{i,j}.

Зверніть увагу на деталь, яку найлегше проґавити: у формулі для R_j береться саме P_{j-1}, а не P_j. Це і кодує вимогу x_3 < x_4 — хвіст мусить стояти строго правіше за рубку.

Відповідь — максимум R_j по всіх рядках і стовпцях.

Складність — . Значення відхилень можуть бути від'ємними, тому ініціалізуйте відповідь «мінус нескінченністю», а не нулем: човен обов'язково має всі три частини, і порожню фігуру брати не можна. Суми накопичуйте у 64-бітному типі.