Изменения

Перейти к: навигация, поиск

Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП

910 байт добавлено, 23:34, 23 декабря 2010
→‎Теорема о связи длины НВП и НУП
|about=
|statement=
Произведение длин наибольшей возрастающей и наибольшей убывающей подпоследовательностей больше либо равно длине последовательностиПусть <tex>a</tex> - последовательность чисел длины <tex>n, l</tex> - длина НВП, <tex>k</tex> - длина НУП. Тогда <tex>l k \geqslant n</tex>.
|proof=
Пусть есть стока Рассмотрим два массива длины <tex> a n : S </tex> длины и <tex> n T </tex>. Рассмотрим наибольшую возрастающую подпоследовательность , где <tex> a[i_1] S_i < a[i_2] /tex> - длина НВП, которая заканчивается на < \dots < a[i_k] tex>a_i</tex> и наибольшую убывающую подпоследовательность , <tex> x[j_1] > x[j_2] > \dots > x[j_l] T_i </tex> строки - длина НУП, которая начинается на <tex> a a_i</tex>.
Докажем, что все пары <tex>(S_i, T_i)</tex> различны.
Пусть существуют такие <tex>i < j</tex> , что <tex> S_i </tex> = <tex> S_j </tex> и <tex> T_i </tex> = <tex> T_j</tex>. Если <tex>a_i < a_j</tex>, тогда <tex> a_j </tex> можно добавить к НВП, заканчивающейся на <tex> a_i </tex>, следовательно <tex>S_j \geqslant S_i + 1</tex>. Если <tex>a_i > a_j</tex>, то по аналогии <tex>T_i \geqslant T_j + 1</tex>. Противоречие! Следовательно все такие пары различны.
 
Заметим что <tex>1 \leqslant S_i \leqslant l, 1 \leqslant T_i \leqslant k</tex>, поэтому существуют <tex>l k</tex> различных пар <tex> (S_i, T_i) </tex>. Если <tex>l k < n</tex> тогда среди <tex> n </tex> пар найдутся две одинаковые. Такого быть не может по доказанному выше, т. е. <tex>l k \geqslant n</tex>, ч. т. д.
}}
Da1s20
13
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/6242»

Навигация