Тереңдетилген динамикалык программалоо
Классикалык ДП: O(n·W) убакыттагы 0/1 рюкзак жана O(n log n) убакыттагы эң узун өсүүчү подпоследовательность.
Бир деңгээл жогору — эки параметрлүү ДП жана оптималдаштыруулары бар ДП. Ар бир олимпиадачы билүүгө милдеттүү эки маселени талдайбыз.
0/1 рюкзак: салмагы жана баалуулугу бар n буюм, сыйымдуулугу W рюкзак; ар бир буюм бир жолу алынат; баалуулукту максималдаштыруу керек.
Абал: dp[cap] — сыйымдуулук cap болгондогу максималдуу баалуулук. Ар бир буюм үчүн dp массивин жаңылайбыз: же албайбыз (эч нерсе өзгөрбөйт), же алабыз — анда dp[cap] = dp[cap - w] + cost.
Маселени талдоонун себеби болгон ичке жагдай: сыйымдуулук боюнча ички цикл ЖОГОРУДАН ТӨМӨН жүрөт. Антпесе буюм бир өтүүдө эки жолу «салынып» кетет.
0/1 рюкзак. Киргизиңиз: 4 8, андан кийин «салмак баалуулук» түгөйлөрү: 3 4, 4 5, 5 6, 2 3
Мисалдагы жооп: 10 (салмагы 3 жана 5 буюмдар: баалуулуктары 4 + 6). Татаалдыгы O(n·W) — көңүл буруңуз: ал сыйымдуулуктун САНДЫК маанисинен көз каранды, ошондуктан рюкзак W миллиондорго чейин болгондо жакшы, бирок W = 10¹⁸ болгондо алсыз.
Экинчи классика — эң узун өсүүчү подпоследовательность (LIS). O(n²) убакыттагы жөнөкөй ДПны баары билет; олимпиадалык версиясы — O(n log n): tail массивин кармайбыз, мында tail[k] — узундугу k+1 болгон өсүүчү подпоследовательностьтун мүмкүн болгон эң кичине аягы. Ар бир жаңы элемент же эң жакшы подпоследовательностьту узартат, же кимдир бирөөнүн аягын жакшыртат — позиция бинардык издөө менен табылат.
O(n log n) убакыттагы LIS. Киргизиңиз: 8, андан кийин 10 9 2 5 3 7 101 18
Мисалдагы жооп: 4 (мисалы, 2 3 7 18). Түшүнүү маанилүү: tail — подпоследовательностьтун ӨЗҮ ЭМЕС, «эң жакшы аяктар» гана; бирок анын узундугу ар дайым LIS узундугуна барабар.
ДП абалдарын кантип ойлоп табуу керек: өзүңүздөн сураңыз — оптималдуу улантуу үчүн чечимдин префикси жөнүндө МИНИМУМ кандай маалымат жетиштүү? Дал ушул — абалдын параметрлери.
Тапшырма: LIS узундугун эмес, подпоследовательностьтун өзүн чыгарыңыз (ар бир элемент үчүн ал кимди узартканын сактаңыз).
Сабакты өттүм деп белгилеңиз.