Eng uzun umumiy quyi-ketma-ketlik (LCS) - Course 3

Modul 1: 2D DP

Eng uzun umumiy quyi-ketma-ketlik (LCS)
Eng uzun o‘suvchi qism ketma-ketlik
$O(N \log N)$ uchun eng uzun o‘suvchi qism ketma-ketlik (LIS)
Ryukzak masalasi
Lazy DP

Modul 2: DSU

DSU - Kesishmaydigan to‘plamlar tizimi

Modul 3: MST

Minimal va maksimal qamrovchi daraxtlar
Kruskal algoritmi
Prima algoritmi
Boruvka algoritmi

Modul 4: Kombinatorika

Yulduzlar va ustunlar
Qo‘shish-ayirish prinsipi

Modul 5: Geometriya

Finding the area of a simple polygon

Modul 6: Uzun sonli arifmetika

Uzun arifmetika

Modul 7: Minimum saqlash uchun strukturalar

Minimumli stek
Minimumli navbat
Minimumli deque

Modul 8: Heap [BONUS]

Heap

Bosh sahifa Kurslar Resurslar Masalalar Milliy olimpiada Musobaqalar Reyting

...

Bosh sahifa/Courses/Course 3/Modul 1: 2D DP/Eng uzun umumiy quyi-ketma-ketlik (LCS)

Eng uzun umumiy quyi-ketma-ketlik (LCS)

Eng uzun umumiy qismketma-ketlik (LCS)

Masala sharti

Ikki ketma-ketlik $a_1, a_2, \ldots, a_n$ va $b_1, b_2, \ldots, b_m$ berilgan. Eng katta umumiy ostketma-ketlik uzunligini topish talab qilinadi.

Up next

Eng uzun o‘suvchi qism ketma-ketlik

Eng uzun o‘suvchi qism-ketma-ketlik

b1,b2,…,bm

Masalan, $[1, 2, 3]$ va $[2, 3, 1]$ ning eng katta umumiy ostketma-ketligi $[2, 3]$ bo‘ladi.

Yechim

$dp(i, j)$ ni $i$ uzunlikdagi $a$ prefiksi va $j$ uzunlikdagi $b$ prefiksi uchun yechim deb belgilaymiz. Ya’ni $a[1 \ldots i]$ va $b[1 \ldots j]$ ning eng katta umumiy ostketma-ketligi uzunligi.

Bazaviy holatlar:

dp(0, j) = 0 \ (0 \leq j \leq m)

dp(i, 0) = 0 \ (0 \leq i \leq n)

Endi umumiy holat $dp(i, j) \ (0 < i \leq n, \ 0 < j \leq m)$ uchun o‘tishlarni topishga harakat qilamiz. Keling, o‘tishlarni ko‘rib chiqamiz:

$a_i$ elementi umumiy ostketma-ketlikka kiritilmagan. Unda $dp(i - 1, j)$ o‘tishga ega bo‘lamiz.
$b_j$ elementi umumiy ostketma-ketlikka kiritilmagan. Unda $dp(i, j - 1)$ o‘tishga ega bo‘lamiz.
$a_i$ va $b_j$ elementlari umumiy ostketma-ketlikka kiritilgan. Bu faqat ular teng bo‘lsa mumkin, ya’ni $a_i=b_j$ . Unda o‘tishga ega bo‘lamiz.

Shunday qilib, formulaga ega bo‘lamiz:

dp(i, j) = \text{max} \begin{cases} dp(i - 1, j) \\ dp(i, j - 1) \\ dp(i - 1, j - 1) + 1 & a_i = b_j \\ \end{cases}

Tiklash bilan NOP

Keling, har bir bazaviy bo‘lmagan holat uchun eng yaxshi o‘tishni eslab qolaylik. Ya’ni biz bilamizki, $dp(i, j)$ uch xil o‘tishga ega:

$dp(i - 1, j)$
$dp(i, j - 1)$
$dp(i - 1, j - 1) + 1)$

Boshqa $p(i, j)$ massivini yaratamiz va $p(i, j)$ da $d(i, j)$ uchun qaysi o‘tish eng yaxshi ekanini saqlaymiz. Masalan, agar $dp(i, j) = dp(i - 1, j - 1) + 1$ bo‘lsa, unda $p(i, j) = 3$ bo‘ladi.

Shundan so‘ng endi biz javobni tiklashimiz mumkin. $x=n, y=m$ ni initsializatsiya qilamiz va $x>0$ va $y>0$ bo‘lguncha quyidagilarni qilamiz.

Agar $p(x, y) == 3$ bo‘lsa, demak biz umumiy ostketma-ketlikka $a_x$ va $b_y$ ni kiritganmiz. Shunday qilib, javobga $a_x$ ni qo‘shamiz va $:x=x-1, y:=y-1$ ga o‘tamiz.
Agar $p(x, y) == 2$ bo‘lsa, $x,y:=y-1$ ga o‘tamiz.
Agar $p(x, y) == 1$ bo‘lsa, $x:=x-1,y$ ga o‘tamiz.

bj

dp(i - 1, j - 1) + 1

=

bj

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = 0;
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            dp[i][j] = max(dp[i][j], dp[i][j - 1]);
            if (a[i] == b[j]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
    }

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = -1;
            if (dp[i - 1][j] > dp[i][j]) {
                dp[i][j] = dp[i - 1][j];
                p[i][j] = 1;
            }
            if (dp[i][j - 1] > dp[i][j]) {
                dp[i][j] = dp[i][j - 1];
                p[i][j] = 2;
            }
            if (a[i] == b[j] && dp[i - 1][j - 1] + 1 > dp[i][j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                p[i][j] = 3;
            }
        }
    }
    vector<int> res;
    int x = n, y = m;
    while (x > 0 && y > 0) {
        if (p[x][y] == 3) {
            res.push_back(a[x]);
            x -= 1;
            y -= 1;
        } else if (p[x][y] == 2) {
            y -= 1;
        } else { // p[x][y] == 1
            x -= 1;
        }
    }
    reverse(res.begin(), res.end());