DP-и ҷузъи пайвастшуда
DP-и ҷузъи пайвастшуда
JOI 2016 — Осмонхарош
Изҳороти масъала
Бо дода шудани , шумораи ҷойивазкуниҳои ин ададҳоро ҳисоб кунед, ки
DP-и ҷузъи пайвастшуда
Бо дода шудани , шумораи ҷойивазкуниҳои ин ададҳоро ҳисоб кунед, ки
ки дар он адади бутуни додашуда аст.
Массивро тартиб диҳед ва унсурҳоро бо тартиби афзоиш ворид кунед.
Мо ҷойивазкуниро бо тартиби қимат, на бо мавқеъ, месозем.
Ҳангоми ворид кардани унсурҳо, мо пайгирӣ мекунем, ки ҳоло чанд компоненти пайвастаи мавқеъҳои пуршуда вуҷуд дорад.
Мисоли як ҷойивазкунии қисман: 1, 2, ?, ?, 3, ?, 5, ?
Дар ин ҷо:
[1,2], [3], [5] → 3 компонентИн дидгоҳ ба мо имкон медиҳад фаҳмем, ки ворид кардани қимати навбатӣ чӣ гуна ҳам сохтор ва ҳам арзишро тағйир медиҳад.
Бигзор
шумораи роҳҳо бошад баъд аз ворид кардани аввалин унсури хурдтарин, ба тавре ки:
? ба баробаранд)Ҳангоми ворид кардани , мо ҳамаи таъсирҳои сохториро ба компонентҳо баррасӣ мекунем:
Ин амалҳо тағйир медиҳанд:
Як ҳилаи калидӣ он аст, ки чӣ гуна мо арзишро самаранок ҳангоми воридкунии қадам ба қадам нигоҳ медорем.
Пеш аз ворид кардани , ҳамаи мавқеъҳои холӣ (?) чунин фарз карда мешаванд, ки қиматашон аст.
Азбаски қиматҳо бо тартиби тартибдодашуда ворид мешаванд, ин камтарин арзиши имконпазир-ро медиҳад, ки бо сохтори ҷорӣ мувофиқ аст.
Вақте ки воқеан ворид мешавад, ҳамаи қиматҳои хушбинона воқеӣ мешаванд.
Ҳар ҳамсоягие, ки ?-ро дар бар мегирад, ба андозаи
зиёд мешавад.
Пас арзиши умумӣ ба андозаи
зиёд мешавад.
Ҳар компоненти пайваста ду канори сарҳадӣ медиҳад. Канорҳои пуршуда як сарҳадро барои ҳар кадом кам мекунанд.
Пас:
Аз ин рӯ:
Аз ҳолати баъд аз навсозии арзиш:
Якҷо кардани ду компонент
Пайваст кардан дар дохили як компонент
Эҷод кардани компоненти нав
Эҷод кардани канори нав (агар )
Дароз кардан то канор (агар )
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;
}