Головна

Знаходження наідліннейшей зростаючої підпослідовності

  1. Завдання 2. Вимірювання в'язкості ліофільного золю при різних значеннях рН середовища. Знаходження ізоелектричної точки
  2. Завдання № 3. Знаходження коренів рівняння з допомогою підбору параметра.
  3. Знаходження коренів алгебраїчних рівнянь.
  4. Знаходження на державній службі. Атестація державних службовців.
  5. Знаходження найбільшою нульовий подматріци
  6. Знаходження обсягу вибіркової сукупності.

Дан масив з  чисел:  . Потрібно знайти в цій послідовності строго зростаючу підпослідовність найбільшої довжини.

int d [MAXN], p [MAXN]; // Константа MAXN дорівнює найбільшому можливому значенню n

for (int i = 0; i

d [i] = 1;

p [i] = -1;

for (int j = 0; j

if (a [j]

if (1 + d [j]> d [i]) {

d [i] = 1 + d [j];

p [i] = j;

}

}

int ans = d [0], pos = 0;

for (int i = 0; i

if (d [i]> ans) {

ans = d [i];

pos = i;

}

cout << ans << endl;

vector path;

while (pos! = -1) {

path.push_back (pos);

pos = p [pos];

}

reverse (path.begin (), path.end ());

for (int i = 0; i <(int) path.size (); ++ i)

cout << path [i] << '';

28) Динаміка за профілем. Завдання "паркет"

int n, m;

vector > d;

void calc (int x = 0, int y = 0, int mask = 0, int next_mask = 0)

{

if (x == n)

return;

if (y> = m)

d [x + 1] [next_mask] + = d [x] [mask];

else

{

int my_mask = 1 << y;

if (mask & my_mask)

calc (x, y + 1, mask, next_mask);

else

{

calc (x, y + 1, mask, next_mask | my_mask);

if (y + 1

calc (x, y + 2, mask, next_mask);

}

}

}

int main ()

{

cin >> n >> m;

d.resize (n + 1, vector (1 << m));

d [0] [0] = 1;

for (int x = 0; x

for (int mask = 0; mask <(1 << m); ++ mask)

calc (x, 0, mask, 0);

cout << d [n] [0];

}

 



Z-функція рядка і її обчислення | Знаходження найбільшою нульовий подматріци

Флойд-Уоршелл | Алгоритм пошуку компонент зв'язності в графі | Пошук точок зчленування | Алгоритм Куна знаходження найбільшого паросполучення в дводольному графі | Розширений Евклід | дискретного логарифмування | Теорема Піка. | Біноміальні коефіцієнти | числа Каталана | намиста |

© um.co.ua - учбові матеріали та реферати