Bitsetlar yordamida optimallashtirish

Bitsetlar yordamida optimallashtirish

G‘oya

std::bitset (yoki uint64_t ustida o‘zingizning bitsetingiz) bizga ko‘plab boolean holatlarni bitta amalda qayta ishlash imkonini beradi.

DP / o‘tishlarni birma-bir katak yangilash o‘rniga, biz bir vaqtning o‘zida 64 bitni (yoki boshqa mashina-so‘z blok o‘lchamini) yangilaymiz, shuning uchun doimiy ko‘paytuvchi ancha yaxshilanadi.

Bu quyidagi holatlarda juda foydali:

• DP holati boolean (reachable / not reachable)
• o‘tishlar shiftlar / OR / AND orqali ifodalanishi mumkin
• cheklovlar yetarlicha katta bo‘lib, doimiylar ahamiyatli bo‘ladi

Misol 1

Masala

$N$ ta buyum berilgan. $i$-buyumning og‘irligi $w_i$. Umumiy og‘irligi aynan $W$ ga teng bo‘lgan qism to‘plam bor-yo‘qligini tekshiring.

Klassik DP