CSES - Johdanto
  • Time limit: 0.00 s
  • Memory limit: MB

Tällä viikolla aloitamme tutustumisen dynaamiseen ohjelmointiin. KKKK:n luvut 21–23 auttavat tehtävissä.

Lukiolaisten Datatähti-kisa käytiin to 29.1. alustana CSES. Jos haluat katsoa kisan tehtäviä, paina tästä. Voit myös kokeilla lähettää omia ratkaisujasi tehtäviin (ne eivät vaikuta tulostauluun, koska kisa on jo ohi).

Vinkit

Kilpailu

[hint]Muodosta rekursiivinen funktio T(k,x)T(k, x), joka on eri tapojen lukumäärä muodostaa summa xx tehtävistä 1k1\ldots k. Käytä dynaamista ohjelmointia vastauksien selvittämiseen TT-funktiolla.[/hint]

Lukujono

[hint]Huomaa, että vain osaa arvoista U0,U1,U2,,Un1U_0, U_1, U_2, \ldots, U_{n-1} tarvitaan arvon UnU_n laskemiseen.[/hint]

Ruudukko

[hint]Laske jokaiseen ruudukon ruutuun aakkosjärjestyksessä pienin siihen päättyvä merkkijono.[/hint]

Unirytmi

[hint]Käytä summataulukkoa nopeuttamaan dynaamista ohjelmointia.[/hint]

Taulukko

[hint]Keksi segmenttipuurakenne, josta voi kysyä suurinta yhtenäisen alueen summaa.[/hint]