Вася і матриця#3535

Вася і матриця (Розбір)

Нехай $a$ — вхідна прямокутна матриця. Створимо двовимірний масив $d p$ такого ж розміру, де $d p [i] [j]$ dp[i][j] — це сума елементів у підматриці з протилежними вершинами в точках $(1, 1)$ та $(i, j)$ . Значення в цьому масиві можна обчислити за наступною формулою:

d p [i] [j] = d p [i - 1] [j] + d p [i] [j - 1] - d p [i - 1] [j - 1] + a [i] [j]

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + a[i][j]

Розглянемо підматрицю масиву $a$ розміром $w \times h$ w \times h. Нехай її протилежні кути знаходяться в точках з координатами $(i, j)$ та $(i + w - 1, j + h - 1)$ (i + w - 1, j + h - 1).

Тоді сума всіх чисел у підматриці обчислюється за формулою:

d p [i + w - 1] [j + h - 1] - d p [i + w - 1] [j - 1] - d p [i - 1] [j + h - 1] + d p [i - 1] [j - 1]

dp[i + w - 1][j + h - 1] - dp[i + w - 1][j - 1] - dp[i - 1][j + h - 1] + dp[i - 1][j - 1]

Розв'язуємо задачу повним перебором. Перебираємо всі можливі розміри підматриці $w \times h$ w \times h, а також усі допустимі координати лівого верхнього кута $(i, j)$ цієї підматриці. За допомогою масиву $d p$ за постійний час визначаємо суму чисел всередині поточної підматриці. Якщо ця сума не перевищує $k$ , то серед усіх таких підматриць запам'ятовуємо максимальну площу.

Однак такий перебір працює за $O (n^{4})$ O(n^4), що надто довго. Ми можемо прискорити його до $O (n^{3} l o g n)$ O(n^3logn) за допомогою бінарного пошуку по ширині $h$ підматриці.

Зафіксуємо лівий верхній кут $(i, j)$ . Позначимо через $g (w, h)$ g(w, h) суму елементів підматриці з вершинами $(i, j)$ та $(i + w - 1, j + h - 1)$ (i + w - 1, j + h - 1). Якщо зафіксувати висоту $w$ , а ширину $h$ розглядати як змінну, то функція $g (w, h)$ g(w, h) буде неспадною по $h$ , так як вихідна матриця $a$ містить невід'ємні цілі числа. Це дозволяє застосувати бінарний пошук для знаходження максимального значення $h$ , при якому $g (w, h) \leq k$ g(w, h) \le k.

Приклад

Наприклад, сума чисел у підматриці з кутами в точках $(2, 2)$ та $(3, 3)$ дорівнює

48 - 19 - 19 + 7 = 17

48 - 19 - 19 + 7 = 17

Реалізація алгоритму

Вхідну матрицю зберігаємо в масиві $a$ .

#define MAX 210
int a[MAX][MAX], dp[MAX][MAX];

Функція $f (w, h)$ f(w, h) повертає $1$ , якщо існує підматриця розміру $w \times h$ w \times h, сума елементів у якій не перевищує $k$ . Для цього перебираються всі можливі координати лівого верхнього кута $(i, j)$ , і за допомогою масиву $d p$ за константний час обчислюється сума елементів у прямокутнику з вершинами $(i, j)$ та $(i + w - 1, j + h - 1)$ (i + w - 1, j + h - 1).

int f(int w, int h)
{
  for (int i = 1; i + w - 1 <= n; i ++)
  for (int j = 1; j + h - 1 <= m; j ++)
    if (dp[i + w - 1][j + h - 1] - dp[i + w - 1][j - 1] –
        dp[i - 1][j + h - 1] + dp[i - 1][j - 1] <= k) return 1;
  return 0;
};

C++

Основна частина програми. Читаємо вхідну матрицю.

scanf("%d %d %d",&n,&m,&k);
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
  scanf("%d",&a[i][j]);

На основі вхідної матриці $a$ обчислюємо допоміжну матрицю $d p$ .

for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
  dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + a[i][j];

Перебираємо можливі значення ширини підматриці $w$ .

answer = 0;
for (w = 1; w <= n; w++)
{

Довжину підматриці перебираємо за допомогою бінарного пошуку на відрізку $[l; r]$ [l; r].

  l = 1; r = m;
  while (l < r)
  {
    mid = (l + r) / 2;

Для підматриці розміром $w \times mi d$ w \times mid перебираємо всі можливі позиції її лівого верхнього кута $(i, j)$ . Якщо існує хоча б одне положення, при якому сума елементів у підматриці не перевищує $k$ , оновлюємо значення результуючої площі $an s w er$ .

    if (f(w,mid))
    {
      answer = max(answer, w * mid);
      l = mid + 1;
    } 
    else r = mid;
  }

  mid = (l + r) / 2;
  if (f(w,mid))
    answer = max(answer, w * mid);
};

C++

Виводимо площу знайденої максимальної підматриці.

printf("%d\n",answer);