Bog‘langan komponentlar bo‘yicha DP
Bog‘langan komponentlar bo‘yicha DP
JOI 2016 — Osmono‘par bino
Masala sharti
berilgan, shunday bu sonlarning nechta permutatsiyasi borligini hisoblangki
Bog‘langan komponentlar bo‘yicha DP
berilgan, shunday bu sonlarning nechta permutatsiyasi borligini hisoblangki
bu yerda — berilgan butun son.
Massivni saralaymiz va elementlarni o‘sish tartibida kiritib boramiz.
Biz permutatsiyani pozitsiyalar bo‘yicha emas, qiymatlar tartibida quramiz.
Elementlarni kiritishda hozir nechta to‘ldirilgan pozitsiyalarning bog‘langan komponentalari mavjudligini kuzatamiz.
Qisman permutatsiya misoli: 1, 2, ?, ?, 3, ?, 5, ?
Bu yerda:
[1,2], [3], [5] → 3 komponentaBunday nuqtai nazar keyingi qiymatni kiritish struktura va qiymatni qanday o‘zgartirishini mulohaza qilishga imkon beradi.
Quyidagicha bo‘lsin
— eng kichik birinchi ta element kiritilgandan keyin shunday usullar soniki:
? lar ga teng deb faraz qilinsa)ni kiritishda komponentalarga ta’sir qiluvchi barcha strukturaviy effektlarni ko‘rib chiqamiz:
Bu amallar quyidagilarni o‘zgartiradi:
Asosiy hiyla — bosqichma-bosqich kiritishda qiymatni qanday samarali ushlab turishimiz.
ni kiritishdan oldin barcha bo‘sh pozitsiyalar (?) qiymatga ega deb hisoblanadi.
Qiymatlar saralangan tartibda kiritilgani uchun, bu joriy struktura bilan mos keladigan eng kichik mumkin bo‘lgan qiymatni beradi.
haqiqatan kiritilganda, barcha optimistik qiymatlar haqiqiy bo‘ladi.
? ni o‘z ichiga olgan har bir qo‘shni juftlik quyidagicha ortadi:
Shuning uchun umumiy qiymat quyidagicha ortadi:
Har bir bog‘langan komponenta ikkita chegaraviy qirra beradi. Band uchlar har biri bittadan chegarani olib tashlaydi.
Demak:
Shunday qilib:
Qiymat yangilangandan so‘ng holatidan:
Ikki komponentani birlashtirish
Komponenta ichida qo‘shish
Yangi komponenta yaratish
Yangi uch yaratish (agar )
Uchgacha uzaytirish (agar )
int solve(int idx, int components, int cost, int filled_ends) {
if (filled_ends > 2 || cost > L) return 0;
if (components == 0 && idx > 1) return 0;
if (idx == n + 1) return filled_ends == 2 && components == 1;
int &ret = dp[idx][components][cost][filled_ends];
if (ret != -1) return ret;
int new_cost = cost + (a[idx] - a[idx - 1]) * (2 * components - filled_ends);
long long ans = 0;
if (components >= 2)
ans += (components - 1) *
solve(idx + 1, components - 1, new_cost, filled_ends);
if (components >= 1)
ans += (2 * components - filled_ends) *
solve(idx + 1, components, new_cost, filled_ends);
ans += (components + 1 - filled_ends) *
solve(idx + 1, components + 1, new_cost, filled_ends);
if (filled_ends < 2) {
ans += (2 - filled_ends) *
solve(idx + 1, components + 1, new_cost, filled_ends + 1);
ans += (2 - filled_ends) *
solve(idx + 1, components, new_cost, filled_ends + 1);
}
return ret = ans;
}