[14 03 2013] Dynamiki

1. Zadanie "Mapa gęstości"

• http://main.edu.pl/pl/archive/oi/8/map
• zapis: S[i][j]=P[i][j]+S[i-1][j]+S[i][j-1]-S[i-1][j-1]
• odczyt: S[b][d]-S[a-1][d]-S[b][c-1]+S[a-1][c-1]

2. Zadanie "Konduktor"

• http://main.edu.pl/pl/archive/oi/16/kon
• szukamy takich trójkątów, które pozwolą zminimalizować straty

3. Zadanie "Działka"

• http://main.edu.pl/pl/archive/oi/9/dzi
• każdy wiersz rozważamy osobno
• korzystamy z tablicy wysokości od najbliższej jedynki
• na stosie trzymamy możliwe początkowe krawędzie
• maksymalizujemy przetwarzany prostokąt

4. Metoda włączeń i wyłączeń

• http://npb-algorytmy.blogspot.com/2008/09/metoda-wcze-i-wycze-cz-i.html