Ochiq va yopiq interval bilan fokus

Ochiq va yopiq interval bilan fokus

Kirish

Ba’zi DP masalalarida biz guruhlar (yoki intervallar) qurishimiz kerak bo‘ladi, bunda yakuniy qiymat har bir guruhning birinchi va oxirgi elementiga bog‘liq bo‘ladi. Buning uchun juda foydali shablon — Intervalni ochish va yopish truki.

G‘oya oddiy:

• Biz elementlarni saralangan tartibda qayta ishlaymiz.
• Biz guruhlarga vaqtincha ochiq bo‘lishiga ruxsat beramiz.
• Keyinroq ularning o‘ng uchi belgilanganida ularni yopamiz.

Bu intervallarning barcha uchlarini aniq kuzatib borishdan qochishga yordam beradi.

Masala sharti

Bizga mahorat darajalari $0$ dan $100$ gacha bo‘lgan $n$ ta dasturchi berilgan. Biz ularni jamoalarga shunday bo‘lib chiqmoqchimizki, umumiy jarima $x$ dan oshmasin.

Jamoa uchun jarima = maksimal va minimal mahorat orasidagi farq.

Umumiy jarima = barcha jamoalar jarimalari yig‘indisi.

Jamoalarni shakllantirishning to‘g‘ri usullari sonini hisoblang.

Asosiy g‘oya

Dasturchilarni mahorat bo‘yicha saralaymiz.
Endi har bir jamoa saralangan tartibda uzluksiz kesmaga aylanadi.

Dasturchilarni chapdan o‘ngga ko‘rib chiqishda:

• ba’zi jamoalar allaqachon yakunlangan
• ba’zi jamoalar hali ham ochiq (biz minimumni tanladik, lekin hali maksimumni emas)