Zadanie

Kubo si, ako každý iný premotivovaný prváčik na Matfyze, zapísal o trošku viac predmetov, než je bežné. Odporúčané predmety? No šak obvi. *klik* Angličtina? Veď som z nej maturoval, kredity zadarmo! *klik* Diferenciálne rovnice? Tie slová som už na gympli počul, to bude easy. *klik* Marek písal, že ide na politológiu? *klik* Čo je toto? História piva?!? To znie zaujímavo…

No ale teraz sa začal školský rok, z Kuba opadla všetká eufória a uvedomil si, že si zapísal tak približne tisíc predmetov a neexistuje ani najmenšia šanca, že by všetkými prešiel. A tak po chvíli veľmi pokojného rozmýšľania prišiel s (ako zvyčajne) geniálnym plánom. Zistí si informácie o každom predmete a vyrobí si detailný študijný plán, ktorý mu maximalizuje počet získaných kreditov!

Ale len o pár minút neskôr si o sebe uvedomil ďalšiu, ešte nepríjemnejšiu, realitu. Pred nástupom si hovoril, ako tvrdo bude pracovať, ako porazí prokrastináciu a stane sa z neho Ačkový žiak. Avšak teraz tu leží na posteli, plánu sa, samozrejme, ani nedotkol, a číta si o tom, ako sa kraby päťkrát nezávisle vyvinuli 1. Ako sa sem dostal? Ani sám nevie. Ale jedno je jasné. Jeho práca opäť padne na vás…

Úloha

Kubo má zapísaných \(n\) predmetov. Každému predmetu prislúcha istý počet kreditov \(k_i\), ktoré Kubo získa za úspešné absolvovanie skúšky z tohto predmetu. Pre každý predmet vieme, že Kubo má ešte \(d_i\) dní do termínu skúšky a že potrebuje \(t_i\) z nich stráviť štúdiom daného predmetu, aby skúšku urobil.

Zistite, aké je najväčšie možné množstvo kreditov, ktoré vie Kubo získať.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 1\,000\)) udávajúce počet predmetov, ktoré má Kubo zapísané.

Každý z nasledujúcich \(n\) riadkov obsahuje tri čísla - \(k_i\), \(d_i\) a \(t_i\) (\(1 \leq k_i \leq 10^6, 1 \leq t_i \leq d_i \leq 20\,000\)) popisujúce jeden predmet.

Úloha má niekoľko sád vstupov, ktoré navyše spĺňajú nasledujúce obmedzenia:

Sada 1 2 3 4
\(n \leq\) \(20\) \(100\) \(1\,000\) \(1\,000\)
\(\max d_i \leq\) \(2\,000\) \(20\,000\) \(2\,000\) \(20\,000\)

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo - maximálny počet kreditov, ktorý dokáže Kubo získať.

Príklad

Input:

3
5 7 5
2 8 4
4 5 4

Output:

6

Prvé 4 dni strávime štúdiom tretieho predmetu a nasledujúce 4 dni štúdiom druhého. Takto spravíme skúšku z oboch z nich a tak získame 6 kreditov. Prvý predmet by nám síce dal najviac kreditov, ale okrem neho by sme nič iné nestihli a tak sa nám to neoplatí.

Bruteforce

Najjednoduchší bruteforce je jednoducho vyskúšať všetky možné priradenia študovaných predmetov ku dňom a skontrolovať, ktoré predmety by sme urobili. Toto je však samozrejme príliš pomalé. Časová zložitosť je \(O(n D^n)\), kde \(D=\max d_i\).

Ako toto vieme zrýchliť?

Lepší bruteforce

Môžeme si všimnúť, že keď už raz začneme študovať nejaký predmet, oplatí sa nám ho celý doštudovať a až potom začínať s ďalším.

Predstavme si totiž, že by v optimálnom riešení existovala dvojica predmetov \(A\) a \(B\), také, že \(A\) sme dokončili skôr ako \(B\), ale ešte pred jeho dokončením sme začali študovať \(B\). Tu vidíme, že keby sme najprv dokončili \(A\), stále by sme mali platné riešenie - \(A\) by sme doštudovali skôr a koniec \(B\) by sa nezmenil. Tu teda vidíme, že existuje optimálne riešenie, v ktorom každý predmet študujeme v jednom kuse.

Toto znamená, že predmety môžeme vnímať ako súvislé bloky. Zaujíma nás teda len to, ktoré predmety sa rozhodneme študovať a v akom poradí.

Z tohoto sa nám formuje rýchlejšie riešenie. Vygenerujeme si všetky podmnožiny predmetov a pre každú z nich všetky jej permutácie. Pre každú z nich si skontrolujeme, že zo všetkých predmetoch v nej urobíme skúšku. Zo všetkých, pre ktoré je odpoveď áno zoberieme tú s najviac kreditmi a tá je riešením. Podľa toho, ako šikovne toto implementujeme sa bude časová zložitosť pohybovať medzi \(O(n!)\) a \(O(n^2 n!)\), čo stále nepostačuje na získanie bodov.

Ďaľšie pozorovanie

Tu ale prichádza na radu druhé kritické pozorovanie. Dokážme si, že v optimálnom riešení budeme predmety študovať v poradí ich skúšok. Keby sme mali predmety \(A\) a \(B\) kde \(A\) má termín skôr ako \(B\) ale \(B\) sa učíme skôr ako \(A\), môžeme ich poradie vymeniť. \(A\) tak dokončíme skôr a \(B\) vtedy, čo pôvodne \(A\). To je ale v poriadku, keďže vieme, že \(A\) má termín skôr ako \(B\). V nasledujúcich riešeniach si teda predmety na začiatku zoradíme a tým pádom nám vypadáva nutnosť riešiť v akom poradí ich budeme študovať.

A tu sa nám pomerne priamočiaro rodí ďalšie riešenie. Prejdeme si všetkými podmnožinami predmetov a pre každú skontrolujeme, či dokážeme všetky jej predmety urobiť. Takéto riešenie má časovú zložitosť okolo \(O(n 2^n)\) a po jeho odovzdaní sme odmenení dvoma bodmi.

Dynamika

A v tomto bode už skúseného KSP-čkara neprekvapí, že optimálnym riešením bude dynamické programovanie.

Zamyslime sa teda, čo by sme chceli mať ako stav tejto dynamiky. Keďže ideme robiť dynamiku, budeme mať nejaké malé podproblémy a budeme ich rozširovať na väčšie. Teda, aby sme vedeli, či vieme do riešenia pridať nejaký predmet budeme potrebovať skontrolovať či by sme ho vôbec stíhali, a teda v stave určite budeme potrebovať mať počet dní zatiaľ strávených štúdiom \(j\). Tiež sa však potrebujeme uistiť, že predmet do jedného riešenia nepridáme dvakrát, tak si pamätajme aj posledný študovaný predmet \(i\). Ak \(i=0\), znamená to, že sme žiadny predmet ešte nevybrali.

Pre \(i=0\) je riešenie jasné - žiadne kredity získať nevieme. Ako teraz spočítame hodnoty stavov s nejakým \(i \geq 1\) ak vieme riešenia pre všetky stavy s menším \(i\)? Najprv si skontrolujeme, či by sme takto vôbec predmet doštudovali pred skúškou, teda či \(j \leq d_i\). Ak nie, hodnota stavu je samozrejme 0. Inak si prejdeme všetkými možnými predošlými predmetmi a zoberieme najlepšiu možnosť - \(\text{dp}[i][j] = \max_{0 \leq x \leq i-1} \text{dp}[x][j-t_i] + k_i\). Toto nám dáva časovú zložitosť \(O(n^2 D)\), čo je dostatočne rýchle na získanie šiestich bodov.

Optimálne riešenie

Optimalizácia, ktorá nám získa posledné dva body je pomerne jednoduchá a podobá sa klasickému 0-1 knapsacku. Prestaňme vynucovať, že \(i\) je posledný predmet – nech len hovorí, že žiadny predmet po ňom sme už nepoužili. Toto ale znamená, že pri prechode nebudeme musieť prechádzať všetky \(x\) menšie ako \(i\), ale len \(x=i-1\), pretože všetky ostatné v ňom budú zahrnuté. Nový prechod tak bude jednoducho \(\text{dp}[i][j] = \max(\text{dp}[i-1][j], \text{dp}[i-1][j-t_i] + k_i)\) ak \(j\leq d_i\), inak proste dp\([i-1][j]\) . Toto nám dáva časovú aj pamäťovú zložitosť \(O(n \log n + n D)\). Môžeme si však všimnúť, že pri počítaní stavov s \(i\) potrebujeme len stav \(i-1\), čo znamená, že ostatné vieme postupne zahadzovať a tak mať pamäťovú zložitosť \(O(n+D)\).

#include <bits/stdc++.h>
using namespace std;

struct Predmet {
    int k, d, t;
    Predmet(int ki, int di, int ti) : k(ki), d(di), t(ti) {}
};

int main() {
    int n;
    cin >> n;

    vector<Predmet> predmety;
    for (int i = 0; i < n; i++) {
        int ki, di, ti;
        cin >> ki >> di >> ti;
        predmety.push_back(Predmet(ki, di, ti));
    }

    // predmety zoradíme podľa di
    sort(predmety.begin(), predmety.end(),
         [](Predmet a, Predmet b) { return a.d < b.d; });

    int D = 0;
    for (auto i : predmety) D = max(D, i.d);

    vector<int> dp(D + 1, 0);

    for (int i = 0; i < n; i++) {
        vector<int> new_dp(D + 1, 0);  // spravíme si novy vektor, aby sme
                                       // nepouzili jeden predmet dvakrat
        for (int t = 0; t <= D; t++) {
            int zaciatok = t - predmety[i].t;
            if (t > predmety[i].d || zaciatok < 0) {
                new_dp[t] = dp[t];
            } else {
                new_dp[t] = max(dp[t], dp[zaciatok] + predmety[i].k);
            }
        }
        dp = new_dp;
    }
    int res = 0;
    // riesenim je maximum celej tabulky
    for (auto i : dp) res = max(res, i);
    cout << res << endl;
}

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ť.