Динамическое программирование

НВП - наибольшая возрастающая подпоследоватеьность

\(i < j < n ... < k\)

\(a_i < a_j ... a_k\)

Используя дерево отрезков на максимум \(O(n \log n)\)

Сожмём массив a

1. sort(a)
2. TODO

b[x] = НВП окончивающийся элементом x

for i in range(n):
    dp[i] = b.get(0, a[i] - 1) + 1
    b.relax(a[i], dp)

\(O(n ^ 2)\)

1. \(d[i]\) - наименьшее число на которое заканчивается НВП размером i
2. Изначально мы полагаем \(d[0] = -\infty\), а все остальные элементы \(d[i] = \infty\).
3. Считать эту динамику мы будем постепенно, обработав число \(a[0]\), затем \(a[1]\), и т.д.

Приведём реализацию этой динамики за \(O (n^2)\):

TODO code-

int d[MAXN];
d[0] = -INF;
for (int i=1; i<=n; ++i)
    d[i] = INF;

for (int i=0; i<n; i++)
    for (int j=1; j<=n; j++)
        if (d[j-1] < a[i] && a[i] < d[j])
            d[j] = a[i];

Используя бинпоиск \(O(n \log n)\)

Используя функцию \(upper_bound\) (который возвращает позицию первого элемента, строго большего данного):

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define INF (long long) 1e18

int main() {
    ll n, t;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<ll> d (n + 1, INF);
    d[0] = -INF;
    vector<ll> p (n);
    vector<ll> no (n + 1);
    no[0] = -1;
    for (ll i = 0; i < n; i++) {
            ll j = upper_bound(d.begin(), d.end(), a[i]) - d.begin() - 1;
            if (d[j] < a[i] && a[i] < d[j + 1]) {
                    d[j + 1] = a[i];
                    p[i] = no[j];
                    no[j + 1] = i;
            }
    }
    vector<int> result;
    for (int i = n; i >= 1; i--)
        if (d[i] != INF) {
            for (int cur = no[i]; cur != -1; cur = p[cur])
                result.push_back (cur);
                break;
            }
    reverse(result.begin(), result.end());
    cout << result.size() << "\n";
    for (unsigned i = 0; i < result.size(); i++)
            cout << result[i] + 1 << " ";
    return 0;
}

---

НОП

НОП - наибольшая общая подпоследовательность

Последовательность \(Z=⟨z_1,z_2,…,z_k⟩\) является подпоследовательностью (англ. subsequence) последовательности \(X=⟨x_1,x_2,…,x_m⟩\), если существует строго возрастающая последовательность \(⟨i_1,i_2,…,i_k⟩\) индексов \(X\) таких, что для всех \(j=1,2,…,k\) выполняется соотношение \(x_{i_j}=z_j\).

Задача:

Пусть имеются последовательности \(X=⟨x_1,x_2,…,x_m⟩\) и \(Y=⟨y_1,y_2,…,y_n⟩\). Необходимо найти \(LCS(X,Y)\)

---

Рюкзак

Дано \(N\) предметов, \(W\) — вместимость рюкзака, \(w={w_1,w_2,…,w_N}\) — соответствующий ему набор положительных целых весов, \(p={p_1,p_2,…,p_N}\) — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин \(B={b_1,b_2,…,b_N}\), где \(b_i=1\), если предмет \(n_i\) включен в набор, \(b_i=0\), если предмет \(n_i\) не включен, и такой что:

1. \(b_1w_1+⋯+b_Nw_N⩽W\)
2. \(b_1p_1+⋯+b_Np_N\) максимальна.

Динамического программирования. \(O(NW)\)

TODO https://neerc.ifmo.ru/wiki/index.php?title=Задача_о_рюкзаке

ДП на подотрезках

строка s PHOTO TODO

Треангуляция

n - вершин многоугольника. Разбить его на треугольники.

1. Сумма отрезков треугольника минимальна
2. Отрезки не пересекаются

Решение

1. dp[i][j] - цена минимальной треангуляции многоугольника от i до j

Дп по числам

числа длинной n, суммa цифр k

1. dp[i][j] - кол-во чисел с суммой цифр j и длинной i

PHOTO TODO