Vasya və matrisa#3535

Vasya və matrisa (Həll təhlili)

Verilən $a$ — giriş düzbucaqlı matrisa olsun. Eyni ölçüdə olan ikiölçülü $d p$ massivini yaratmaq lazımdır, burada $d p [i] [j]$ dp[i][j] — $(1, 1)$ və $(i, j)$ nöqtələrində yerləşən düzbucaqlının tərkibində olan elementlərin cəmi olacaq. Bu dəyərlər aşağıdakı formada hesablana bilər:

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$ massivinin $w \times h$ w \times h ölçülü altmatrisasına nəzər salaq. Onun qarşı tərəflərini $(i, j)$ və $(i + w - 1, j + h - 1)$ (i + w - 1, j + h - 1) koordinatlarında olmaqla qəbul edək.

Onda altmatrisanın içindəki bütün ədədlərin cəmi belə hesablanır:

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]

Məsələni tam təkrarlı yol ilə həll edək. Altmatrisanın mümkün olan bütün $w \times h$ w \times h ölçülərini, həmçinin altmatrisanın sol üst köşə koordinatlarını $(i, j)$ nəzərdən keçiririk. $d p$ massivindən istifadə edərək, cari altmatrisanın daxilindəki ədədlərin cəmini sabit zamanda müəyyən edirik. Əgər bu cəm $k$ -dan çox deyilsə, belə altmatrisaların içində maksimum sahəni yadda saxlayırıq.

Amma belə bir təkrar $O (n^{4})$ O(n^4) zaman fəzasında işləyir, bu da çox uzundur. Bunu $O (n^{3} l o g n)$ O(n^3logn)-ə qədər sürətləndirə bilərik, altmatrisanın eni $h$ üçün ikitərəfli axtarışdan istifadə edərək.

Sol üst köşə nöqtəsini $(i, j)$ sabitləyirik. $g (w, h)$ g(w, h) funksiyası ilə $(i, j)$ və $(i + w - 1, j + h - 1)$ (i + w - 1, j + h - 1) köşə daxilindəki elementlərin cəmini təyin edək. Əgər hündürlüyü $w$ sabitləyərək, eni $h$ kimi qəbul etsək, $g (w, h)$ g(w, h) funksiyası $h$ -yə görə artan olacaq, çünki ilkin matrisa $a$ mənfi olmayan tam ədədlərdən ibarətdir. Bu, $g (w, h) \leq k$ g(w, h) \le k olan maksimum $h$ dəyərini tapmaq üçün ikitərəfli axtarışdan istifadə etməyə imkan verir.

Misal

Məsələn, $(2, 2)$ və $(3, 3)$ nöqtələr ilə ifadə olunan altmatrisanın daxilindəki ədədlərin cəmi

48 - 19 - 19 + 7 = 17

48 - 19 - 19 + 7 = 17

Alqoritmin icrası

Giriş matrisasını $a$ massivində saxlayırıq.

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

Funksiya $f (w, h)$ f(w, h) $w \times h$ w \times h ölçüsündəki bir altmatrisanın mövcudluğunu, sayları $k$ -dan çox olmayacaq şəkildə yoxlayır. Bütün mümkün sol köşə koordinatlarını $(i, j)$ nəzərdən keçirərək və $d p$ massivindən istifadə edərək verilmiş düzbucaqlı daxilindəki ədədlərin cəmini sabit zamanda hesablayırıq.

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++

Proqramın əsas hissəsi. Giriş matrisasını oxuyuruq.

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

Verilən giriş matrisasına əsasən $d p$ dəst matrisa yaradırıq.

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];

Mümkün altmatrisanın eni olan $w$ dəyərlərini nəzərdən keçiririk.

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

Altmatrisanın uzunluğunu $[l; r]$ [l; r] aralığında ikitərəfli axtarışla nəzərdən keçiririk.

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

$w \times mi d$ w \times mid ölçülü altmatrisanın sol üst köşəsi $(i, j)$ -ın bütün mümkün mövqelərini nəzərdən keçiririk. Əgər hər hansı bir mövqe mövcud olsa və altmatrisanın daxilində olan ədəd cəmi $k$ -dan çox deyilsə, nəticənin sahə dəyərini $an s w er$ ilə yeniləyirik.

    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++

Tapılan maksimum altmatrisanın sahəsini çıxardırıq.

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