Бузургтарин зерпайдарпаии умумӣ (БЗУ) - Course 3

Module 1: 2D DP

Бузургтарин зерпайдарпаии умумӣ (БЗУ)
Бузургтарин зерпайдарпаии афзоянда (БЗА)
Зерпайдарпаии афзояндаи калонтарин (ЗАК) дар $O(N \log N)$
Масъалаи ҷузвдон
Lazy DP

Module 2: DSU

Системаи маҷмӯаҳои ғайрибуришкунанда

Module 3: MST

Дарахтони остовии ҳадди ақал ва ҳадди аксар
Алгоритми Крускал
Алгоритми Прим
Алгоритми Борувка

Module 4: Combinatorics

Ситораҳо ва сутунҳо
Принсипи дохилкунӣ-истисноӣ

Module 5: Geometry

Ёфтани масоҳати бисёркунҷаи оддӣ

Module 6: Arbitrary-Precision Arithmetic

Арифметикаи дароз

Module 7: Data structures for keeping minimum

Стек бо ҳадди ақал
Навбат бо ҳадди ақал
Дек бо минимум

Module 8: Heap [BONUS]

Кӯдаи дуӣ

Асосӣ Курсҳо Манбаъҳо Масъалаҳо Олимпиадаи миллӣ Мусобиқаҳо Ҷадвали роҳбарон

...

Асосӣ/Courses/Course 3/Module 1: 2D DP/Бузургтарин зерпайдарпаии умумӣ (БЗУ)

Бузургтарин зерпайдарпаии умумӣ (БЗУ)

Бузургтарин зерпайдарпайии умумӣ (БЗУ)

Шарти масъала

Дода шудаанд ду пайдарпайӣ $a_1, a_2, \ldots, a_n$ ва $b_1, b_2, \ldots, b_m$ . Талаб мешавад дарозии калонтарин зерпайдарпайии умумиро ёфтан.

Up next

Бузургтарин зерпайдарпаии афзоянда (БЗА)

Бузургтарин зерпайдарпаии афзоянда (БЗА)

b1,b2,…,bm

Масалан, калонтарин зерпайдарпайии умумии $[1, 2, 3]$ ва $[2, 3, 1]$ ин $[2, 3]$ мебошад.

Ҳал

$dp(i, j)$ -ро ҳамчун ҳал барои префикси $a$ бо дарозии $i$ ва префикси $b$ бо дарозии $j$ ишора мекунем. Яъне, дарозии калонтарин зерпайдарпайии умумии $a[1 \ldots i]$ ва $b[1 \ldots j]$ .

Ҳолатҳои базавӣ инҳоянд:

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

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

Акнун кӯшиш мекунем гузаришҳоро барои ҳолати умумӣ $dp(i, j) \ (0 < i \leq n, \ 0 < j \leq m)$ пайдо кунем. Биёед гузаришҳоро баррасӣ кунем:

Элементи $a_i$ ба зерпайдарпайии умумӣ дохил нашудааст. Он гоҳ гузариш $dp(i - 1, j)$ -ро дорем.
Элементи $b_j$ ба зерпайдарпайии умумӣ дохил нашудааст. Он гоҳ гузариш $dp(i, j - 1)$ -ро дорем.
Элементҳои $a_i$ ва $b_j$ ба зерпайдарпайии умумӣ дохил шудаанд. Ин танҳо дар ҳолате мумкин аст, ки онҳо баробар бошанд, яъне $a_i=b_j$ . Он гоҳ гузариш -ро дорем.

Пас, формуларо дорем:

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}

НОП бо барқарорсозӣ

Биёед барои ҳар як ҳолати ғайрибазавӣ гузариши беҳтаринро дар хотир нигоҳ дорем. Яъне, мо медонем, ки $dp(i, j)$ се гузариши гуногун дорад:

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

Масиви дигар $p(i, j)$ -ро месозем ва дар $p(i, j)$ нигоҳ медорем, ки кадом гузариш барои $d(i, j)$ беҳтарин аст. Масалан, агар $dp(i, j) = dp(i - 1, j - 1) + 1$ бошад, он гоҳ $p(i, j) = 3$ дорем.

Пас аз ин мо метавонем ҷавобро барқарор кунем. $d(i, j)$ -ро инициализатсия мекунем ва то он даме, ки $x>0$ ва $y>0$ бошад, корҳои зеринро мекунем.

Агар $p(x, y) == 3$ бошад, пас мо ба зерпайдарпайии умумӣ $a_x$ ва $b_y$ -ро дохил карда будем. Пас, $a_x$ -ро ба ҷавоб илова мекунем ва ба $:x=x-1, y:=y-1$ мегузарем.
Агар $p(x, y) == 2$ бошад, пас ба $x,y:=y-1$ мегузарем.
Агар $p(x, y) == 1$ бошад, пас ба $x:=x-1,y$ мегузарем.

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());