Pretpostavimo da radimo dinamiku gdje je stanje bitmaska – koje smo elemente već iskoristili, a u prijelazu biramo neki podskup neiskorištenih elemenata.
Na prvi pogled složenost je 2N * 2N = 4N, ali ne i ako prijelaz pišemo ovako:
for (int nova = 0; nova < (1 << N); nova = (nova + mask + 1) & ~mask) { ... }
To će iterirati po svim podskupovima koji su disjunktni s mask. Ako ovdje ne želimo nulu, treba početi od nova = (mask + 1) & ~mask. Probajte na papiru razumjeti ove petlje i zašto funkcioniraju, inače ih vjerojatno nećete zapamtiti.
Ukupna je složenost O(3N). Ako ne vjerujete, zavrtite ovo:
int cnt = 0; for (int mask = 0; mask < (1 << N); mask++) for (int nova = 0; nova < (1 << N); nova = (nova + mask + 1) & ~mask) ++cnt;
…i možete se uvjeriti da će cnt biti točno 3N. Dokaz slobodno ostavite u komentarima.
Primjer zadatka: Z-most.
Tu, međutim, nije kraj optimizaciji — još efikasniji pristup, složenosti O(N * 2N), i mnogo zadataka (uključujući jedan s HONI/COCI) možete pronaći ovdje. Hvala Patriku Paviću na ovim linkovima.
Povratni ping: Kategorizacija blogaritamskih objava | Blogaritam