Zadanie
Bubu sa rozhodol, že si zaobstará nejaké tie strieborné bubáky. Lenže bubáky nerastú len tak na strome. Pre bežných smrteľníkov je dosť náročná úloha niekde také bubáky zohnať. Bubu však nie je žiadny amatér a vie, ako na to.
Existuje totiž stará baňa, v ktorej trpaslíci zakopali svoje poklady. A Bubuho plán je ich vykopať. Miesto už pozná, potrebuje si už len zaobstarať správne vybavenie, konkrétne dobrý krompáč. Čím lepší krompáč, tým viac ním Bubu vyťaží. Lenže lepšie krompáče zvyčajne aj viac stoja.
Bolo by treba vymyslieť optimálnu stratégiu nakupovania krompáčov. Bubu by si to v skutočnosti vedel spočítať aj sám, ale zrovna sa mu nechce. A tak prichádzate do hry vy.
Úloha
Na začiatku (v deň 0) má Bubu našetrených \(B\) strieborných bubákov.
Na trhu sa dá zohnať \(N\) krompáčov. Krompáč \(i\) (\(1 \leq i \leq N\)) bude dostupný iba v deň \(i\), stojí \(c_i\) bubákov a Bubu ním vykope \(b_i\) bubákov za deň. Bubu si môže kúpiť nový krompáč iba v prípade, že má dosť peňazí, t.j. ak má aspoň \(c_i\) bubákov. Keď tak spraví, starý krompáč okamžite zahodí a potom používa nový krompáč, až kým ho znovu nevymení za ďalší.
Koľko najviac bubákov vie mať Bubu v deň \(N+1\), ak zvolí správne dni, kedy nakúpiť krompáče?
Formát vstupu
V prvom riadku je \(N\) a \(B\) - počet krompáčov a začiatočný počet bubákov. Nasleduje \(N\) riadkov, v \(i\)-tom z nich sú dve čísla \(c_i, b_i\) - cena \(i\)-teho krompáča a počet bubákov, ktoré ním Bubu vykope za deň.
Formát výstupu
Vypíšte jedno číslo - najväčší počet bubákov, ktorý vie mať Bubu v deň \(N+1\).
Hodnotenie
V prvej sade platí \(1 \leq N \leq 1\,000\), \(1 \leq c_i, b_i \leq 1\,000\).
V druhej sade platí \(1 \leq N \leq 200\,000\), \(1 \leq c_i, b_i \leq 10^9\).
Príklady
Input:
5 10
1 1
11 100
11 10
1 5
20 15
Output:
30
V prvom dni si Bubu kúpi krompáč. V druhom dni si nemôže dovoliť krompáč za \(11\), ale v treťom dni už áno a kúpi si ho. Tým za ďalšie tri dni vyťaží \(30\) bubákov. Ak by si kúpil krompáč aj v posledný deň, vedel by ním síce ťažiť viac, ale stojí \(20\) bubákov, a tak by skončil v deň \(N+1\) len s \(15\) bubákmi.
Dynamika
Prvá vec, ktorá pravdepodobne skúsenému riešiteľovi napadne, keď sa pozrie na túto úlohu je: “dynamické programovanie”. Otázkou len je, ako si dobre zadefinovať stavy, aby sme si z menších stavov vedeli jednoducho vypočítať väčšie. Jednoduchý plán by bol definovať \(dp[t]\) = najväčší počet bubákov, ktorý viem mať v deň \(t\) (t.j. po \(t\) použitiach nejakého krompáča, hneď po tom ako sme sa rozhodovali, či kupujeme krompáč v deň \(t\)). Avšak, \(dp[t]\) nevieme priamočiaro vypočítať iba z predošlých stavov. Pri úvahách záleží na tom, ktorý krompáč použijeme zo dňa \(t-1\) na deň \(t\). Preto sa núka zadefinovať stavy nasledovne:
\(dp[t][j] =\) náš najväčší možný počet bubákov v deň \(t\), ak aktuálne máme krompáč \(j\) (ten, ktorý bolo možné kúpiť v deň \(j\))
Môžeme to vnímať tak, že na začiatku máme krompáč \(0\), ktorý ťaží \(0\) bubákov za deň. Teraz vieme medzi stavmi jednoducho prechádzať:
- pre \(j < t\): \(dp[t][j] = dp[t-1][j]+b_j\),
- pre \(j = t\): \(dp[t][j] = -c_t+\max \lbrace dp[t][0], \dots, dp[t][t-1] \rbrace\),
- pre \(j > t\): \(dp[t][j] = -\infty\).
Takže môžeme počítať odpoveď pre jednotlivé stavy podľa \(t\) vzostupne a pre fixné \(t\) vzostupne podľa \(j\). Nakoniec finálnu odpoveď nájdeme ako \(\max \lbrace dp[N+1][0], \dots dp[N+1][N] \rbrace\). Časová zložitosť tohoto riešenia je \(O(N^2)\).
Už to len zrýchliť
Pokúsime sa vylepšiť naše doterajšie riešenie. Chceli by sme dátovú štruktúru. Tá by si udržovala aktuálny deň \(t\), pre tento aktuálny deň naše možnosti zodpovedajúce dvojiciam \((j, dp[t][j])\), kde \(j \leq t\) reprezentuje náš aktuálny krompáč (posledný, ktorý sme sa rozhodli kúpiť). Navyše chceme, aby sa táto štruktúra dala ľahko upraviť pri prechode do dňa \(t+1\).
Ak by sme si pre každý krompáč \(j\) skutočne stále pamätali \(dp[t][j]\), tak by bol update z \(t\) na \(t+1\) časovo náročný (priamočiaro to nejde lepšie ako v \(O(N)\)). Skúsme sa toho teda vzdať. Napriek tomu však budeme chcieť byť schopný (pri troche úsilia) v aktuálnom dni vypočítať hodnotu \(dp[t][j]\) pre ľubovoľné \(j\).
Pre konkrétne \(j\) sa \(dp\) v čase vyvíja priamočiaro. \(dp[j][j]\) treba vypočítať náročne, ale potom je to už jednoduché: \(dp[t][j] = (t-j)b_j+dp[j][j]\). To nás navádza na myšlienku, že v našej štruktúre bude stačiť mať pre fixné \(j\) iba hodnotu \(dp[j][j]\).
Update z času \(t\) na \(t+1\) sa tak zvrháva na to, ako pridať \(t+1\). Ako spočítať \(dp[t+1][t+1]\)? Toto je ťažká vec. Na to, aby sme to vedeli rátať by bolo dobré mať krompáče v našej štruktúre utriedené podľa ich aktuálnej hodnoty \(dp\). Potom by výpočet bol triviálny. Chceš \(dp[t+1][t+1]\)? Zober zo štruktúry (v čase \(t+1\), pred pridaním krompáča \(t+1\)) krompáč \(j_0\) s najväčším \(dp[t+1][j_0]\). Potom \(dp[t+1][t+1] = dp[t+1][j_0]-c_{t+1}\). Ako však udržiavať štruktúru utriedenú?
Vezmime fixný deň \(t\). Krompáč \(j \leq t\) nazvime nadbytočný, ak
- existuje krompáč \(k \leq t\) taký, že (\(dp[t][k] > dp[t][j]\) a \(b_k \geq b_j\)) alebo (\(dp[t][k] = dp[t][j]\) a \(b_k > b_j\)), ALEBO
- existuje krompáč \(k \leq t\) taký, že \(dp[t][k] = dp[t][j]\) a \(b_k = b_j\) a \(k > j\).
Ak sa nám v nejakom čase stane, že je nejaký krompáč nadbytočný, tak na neho môžeme navždy zabudnúť. A presne to aj budeme robiť.
Navyše si všimnime, že ak v čase \(t\) máme v štruktúre iba nenadbytočné krompáče a utriedime ich podľa \(b_j\), tak ich hodnoty \(dp[t][j]\) musia v tomto poradí (nie nutne ostro) klesať. Skutočne, ak \(b_j \leq b_k\) a zároveň \(dp[t][j] \leq dp[t][k]\), tak aspoň jeden z nich je nadbytočný. Takže nám stačí udržovať nenadbytočné krompáče utriedené podľa ich \(b_j\), v prípade zhody podľa \(j\) vzostupne. Konkrétna implementácia môže byť napríklad ako set
v C++ (binárny vyvažovaný strom) s prvkami tvaru \((b_j, j)\).
Ako si však udržovať v štruktúre iba nenadbytočné krompáče? Deň sa práve zmenil z \(t\) na \(t+1\), ešte sme však nepridali krompáč \(t+1\). Potrebujeme spraviť dve úpravy:
- Odstránenie nadbytočných krompáčov: V štruktúre máme krompáče \(j_0, \dots, j_m\) zoradené podľa \(b_j\). Ak sa nejaký krompáč \(j_i\) stal nadbytočným, tak si všimnime, že je nadbytočný s krompáčom \(k = j_{i+1}\) (v definícii vyššie). Budeme preto udrživať set udalostí \(U\), v ktorom pre každý krompáč \(j_i\) v našej štruktúre budeme mať udalosť \((t_*, j_i)\) hovoriacu, že v čase \(t_*\) sa \(j_i\) stane nadbytočným (s \(k = j_{i+1}\)). Potom vieme ľahko spraviť úpravu poradia: Pokiaľ je v \(U\) udalosť s časom \(\leq\) ako \(t+1\), vezmi príslušný krompáč, odstráň ho z poradia a updatni udalosti \(U\).
- Pridanie krompáču \(t+1\) a odstránenie tým vzniknutých nadbytočných krompáčov: Toto je jednoduché. Pozrieme sa kam do poradia by patril \(t+1\). Ten je buď hneď nadbytočný (v takom prípade ho nepridáme vôbec), alebo nie je (v takom prípade ho pridáme a prípadne povyhadzujeme krompáče, ktoré sa tým stali nadbytočné (tie sú nutne v poradí susedné pod ním)).
Poznamenajme, že nám nevadí, keď v konkrétnej implementácii budú pre nejaké \(j_*\) v \(U\) zostávať aj zastaralé udalosti.
Zhrnutie
Udržujeme si aktuálny deň \(t\), nenadbytočné krompáče v poradí podľa \((b_j, j)\) a set udalostí \(U\).
Update z \(t\) na \(t+1\) vyzerá nasledovne:
- Pokiaľ je v \(U\) udalosť s \(t_* \leq t+1\), vyhoď príslušný krompáč zo štruktúry (stal sa nadbytočný) a pridaj nové udalosti do \(U\). Opakuj.
- Nájdi \(j_0\) s najmenším \(b_{j_0}\) (a preto najväčším \(dp[t+1][j_0]\)), z toho spočítaj \(dp[t+1][t+1]\).
- Ak \(t+1\) nie je nadbytočný, pridaj ho a povyhadzuj krompáče, ktoré sa stali nadbytočné (v poradí susedné pod ním).
Na konci (v dni \((N+1)\)), jednoducho nájdeme \(j_0\) s najmenším \(b_{j_0}\) a odpoveď bude \(dp[N+1][j_0]\).
Celkovo spravíme \(O(N)\) operácii s oboma setmi a tieto operácie sú v \(O(\log N)\). Celková zložitosť bude \(O(N \log N)\). Pamäťová zložitosť bude \(O(N)\).
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ff first
#define ss second
struct State {
int time;
// optimal miners: {miner_income, miner_id}
// redundant miners: {time, miner_id}
<pair<ll, int>> optimal_miners, redundant_miners;
set<ll> price, income, base_income;
vector
(int id) {
ll miner_valuereturn (time-id)*income[id]+base_income[id];
}
(int down_id, int up_id) {
ll get_swap_timeif(income[up_id] == income[down_id]) return 0;
double temp_time = (base_income[down_id]-down_id*income[down_id])-(base_income[up_id]-up_id*income[up_id]);
/= income[up_id]-income[down_id];
temp_time = max((ll) 0, (ll) ceil(temp_time));
ll T return T;
}
void add_miner(int id) {
= miner_value(optimal_miners.begin()->ss);
ll val if(val < price[id]) return;
[id] = val-price[id];
base_incomeauto up_it = optimal_miners.upper_bound({income[id], INT_MIN});
if(up_it != optimal_miners.end()) {
if(miner_value(up_it->ss) >= miner_value(id)) return;
= get_swap_time(id, up_it->ss);
ll T .insert({T, id});
redundant_miners}
if(up_it == optimal_miners.begin()) {
.insert({income[id], id});
optimal_minersreturn;
}
auto down_it = prev(up_it);
= get_swap_time(down_it->ss, id);
ll T .insert({T, down_it->ss});
redundant_miners.insert({income[id], id});
optimal_miners}
void remove_miner(int id) {
<ll, int> curr = {income[id], id};
pairif(optimal_miners.find(curr) == optimal_miners.end()) return;
.erase(curr);
optimal_minersauto up_it = optimal_miners.upper_bound(curr);
if(up_it == optimal_miners.end() || up_it == optimal_miners.begin()) return;
auto down_it = prev(optimal_miners.upper_bound(curr));
int up_id = up_it->ss, down_id = down_it->ss;
= get_swap_time(down_id, up_id);
ll T .insert({T, down_id});
redundant_miners}
void simplify() {
while(redundant_miners.size() > 0) {
auto curr = *redundant_miners.begin();
if(curr.ff > time) break;
.erase(curr);
redundant_minersint id = curr.ss;
(id);
remove_miner}
}
};
int main() {
int N; ll B;
>> N >> B;
cin ;
State s.time = 0;
s.optimal_miners.insert({0, 0});
s.price.resize(N+1);
s.income.resize(N+1);
s.base_income.resize(N+1, 0);
s.base_income[0] = B;
sfor(int t = 1; t <= N; t++) {
>> s.price[t] >> s.income[t];
cin .time = t;
s.simplify();
s.add_miner(t);
s.simplify();
s}
.time++;
s.simplify();
s<< s.miner_value(s.optimal_miners.begin()->ss) << "\n";
cout return 0;
}
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.