Eng uzun o‘suvchi qism ketma-ketlik - 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 o‘suvchi qism ketma-ketlik

Eng uzun o‘suvchi qism ketma-ketlik

Eng uzun o‘suvchi qism-ketma-ketlik

Masala sharti

$a_1, a_2, \ldots, a_n$ ketma-ketligi berilgan. Uning eng katta uzunlikdagi o‘suvchi ostketma-ketligini topish talab qilinadi.

Masalan, $[2, 4, 1, 4, 2,$ ning eng katta o‘suvchi ostketma-ketligi bo‘ladi.

Up next

$O(N \log N)$ uchun eng uzun o‘suvchi qism ketma-ketlik (LIS)

Eng uzun o'suvchi qism ketma-ketlik (LIS) $O(N \log N)$ vaqt ichida

3

,

6

,

10

]

[2, 4, 1, 4, 2, 3, 6, 10]

[2, 4, 1, 4, 2, 3, 6, 10]

[1, 2, 3, 6, 10]

Yechim

Yechim 1

$a$ ketma-ketligining nusxasini yaratamiz va o‘sish tartibida saralaymiz. Uni $b$ deb ataymiz. Unda asl masala uchun javob $a$ va $b$ ketma-ketliklarining NOPi bo‘ladi.

Yechim 2

$dp(i)$ ni $a$ massivining uzunligi $i$ bo‘lgan prefiksi uchun yechim deb belgilaymiz, shart shuki, $i$ pozitsiyadagi element javobga kiritilgan bo‘lsin. Ya’ni $a[1 \ldots i]$ ning eng katta o‘suvchi ostketma-ketligi uzunligi, bunda $a_i$ javobga kiritilgan.

Bazaviy holat:

dp(0)=0

Endi umumiy holat $dp(i) \ (0 < i \leq n)$ uchun o‘tishlarni topishga harakat qilamiz. Keling o‘tishlarni tahlil qilamiz. $dp(i)$ ta’rifiga ko‘ra biz javobga $a_i$ ni kiritishimiz kerak. Ya’ni $a[1 \ldots i]$ prefiksining o‘suvchi ostketma-ketligining oxirgi elementi bu $a_i$ . Unda ikki holat bor:

$a[1 \ldots i]$ prefiksining o‘suvchi ostketma-ketligi faqat $a_i$ dan iborat. Unda $dp(i) = 1$ .
Aks holda $a[1 \ldots i]$ prefiksining o‘suvchi ostketma-ketligining oxiridan oldingi elementini ko‘rib chiqamiz. Ya’ni $0 < j < i$ va $a_j < a_i$ bo‘lgan barcha $j$ larni ko‘rib chiqamiz. Shunday $j$ lar orasidan maksimal $dp(j)$ ni olamiz. Unda $dp(i) = dp(j) + 1$ .

Demak, formula:

dp(i) = \text{max} \begin{cases} 1 \\ dp(j) + 1 & 0 < j < i, \ a_j < a_i \\ \end{cases}

Javob barcha $i \ (1 \leq i \leq n)$ lar orasidagi $dp(i)$ ning maksimal qiymati bo‘ladi.

Tiklash bilan NVO

Keling, har bir bazaviy bo‘lmagan holat uchun NOP holatidagi kabi eng yaxshi o‘tishni ham eslab qolamiz. Ya’ni $p(i)$ massivini ham yaratamiz, unda qaysi o‘tish qilinganligi haqidagi ma’lumotni saqlaymiz. Biz bilamizki, $dp(i)$ ning ikki xil o‘tishi bor:

$dp(i) = 1$ . Ya’ni bitta elementdan iborat. Bu holda $p(i):=0$ deb yozamiz.
$dp(i) = dp(j) + 1$ qandaydir $j$ uchun. Unda $p(i):=j$ deb yozamiz.

Shundan so‘ng endi biz javobni tiklay olamiz. $dp(x)$ maksimal qiymatga ega bo‘lgan shunday $x$ ni topamiz. Va $x>0$ bo‘lguncha quyidagini qilamiz.

Javobga $a_x$ ni kiritamiz. Chunki dinamika ta’rifiga ko‘ra bu javobga kiradi. Keyin $x:=p(x)$ ga o‘tamiz.

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

for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        p[i] = 0;
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                p[i] = j;
            }
        }
    }

    int x = 1;
    for (int i = 1; i <= n; i++) {
        if (dp[i] > dp[x]) {
            x = i;
        }
    }

    vector<int> res;
    while (x > 0) {
        res.push_back(a[x]);
        x = p[x];
    }
    reverse(res.begin(), res.end());