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
ta buyum berilgan. -buyumning og‘irligi . Umumiy og‘irligi aynan ga teng bo‘lgan qism to‘plam bor-yo‘qligini tekshiring.