หมายความว่าถ้าผลไม้นี้ถอนพิษขนานที่ ABC ได้ ก็ย่อมถอน AB, AC, BC, A, B, C ได้เช่นกัน เพราะงั้น state การเก็บการถอนพิษน่าจะต้องเก็บเป็น set เลย
ซึ่ง set ในรูปแบบนี้สามารถเก็บเป็น std::vector<bool> ได้แต่ถ้าขนาดไม่เยอะก็เก็บเป็น bitmask ได้เช่นกัน
หน้าตาการเป็น subset จะหน้าตาประมาณนี้
จากโจทย์สุดท้ายจำคำนวนคำตอบได้ต้องรู้ทุกแบบของจุดเริ่มต้นไปจุดจบอยู่ดี แต่ถ้าเราเริ่มจากจุดสุดท้ายย้อนกลับมา จะได้คำตอบของทุกจุดเริ่มต้น
Dijkstra Algorithmเป็นการหา shoteset path โดยวิธี greedy จากจุดเริ่มต้นใดๆ ไปหาทุกจุดอื่นๆในกราฟ
ข้อนี้เลยใช้ Dijkstra on Set (bitmask / bitset)
ข้อนี้ง่ายๆเลยมองให้ state เป็น set
แล้วก็แทนที่จะเริ่มทดลองจากหลายแอปเปิลลูกแรกที่กิน มันยาก ก็ให้เริ่มจากตอนที่หายแล้วไม่มีพิษ แล้วทำนย้อนกลับไปหาว่า พิษมาจากไหนบ้าง
คิดว่าข้อนี้แจกแจงให้ดูเยอะๆเอาน่าจะเห็นภาพง่ายกว่า
เช่นตัวอย่างแรก
id weight from to description
น้ำหนัก ยาพิษ ยาถอน
1.) 1 110 000 ถ้ามีพิษชนิด 000 แล้วกินแอปเปิลผลที่ 1 จะเปลี่ยนเป็นพิษ 110 (มีแต่พิษ)
2.) 3 000 010 ถ้ามีพิษชนิด 0?0 แล้วกินแอปเปิลผลที่ 2 จะเปลี่ยนเป็นพิษ 000
3.) 4 001 110 ถ้ามีพิษชนิด ??0 แล้วกินแอปเปิลผลที่ 3 จะเปลี่ยนเป็นพิษ 001
4.) 5 000 111 ถ้ามีพิษชนิด ??? แล้วกินแอปเปิลผลที่ 4 จะเปลี่ยนเป็นพิษ 000 (หายป่วย)
5.) 7 000 001 ถ้ามีพิษชนิด 00? แล้วกินแอปเปิลผลที่ 5 จะเปลี่ยนเป็นพิษ 000 (หายป่วย)
สร้างกราฟ
000 => {001, w=7}, {111, w=5}, {010, w=3}
001 => {110, w=4}
010
011
100
101
110 => {000, w=1}
111
ทำ dijktra เริ่มจาก 000
000 = 0
pq += {001, w=0+7}, {111, w=0+5}, {010, w=0+3} กิน apple
pq += {} เพิ่ม subset ที่ขนาดเล็กลง
010 = 3
pq = {001, w=7}, {111, w=5}
pq += {} กิน apple
pq += {} เพิ่ม subset ที่ขนาดเล็กลง
111 = 5
pq = {001, w=7}
pq += {} กิน apple
pq += {011, w=5+0}, {101, w=5+0}, {110, w=5+0} เพิ่ม subset ที่ขนาดเล็กลง
011 = 5
pq = {001, w=7}, {101, w=5}, {110, w=5}
pq += {} กิน apple
pq += {001, w=5+0}, {010, w=5+0} เพิ่ม subset ที่ขนาดเล็กลง
หลังจากนี้ทุกอันก็มีค่าเป็น 5 แล้วเพราะว่า 111 กระจายไปหาทุกตัวได้
หลังจากนั้นก็วนผลไม่ทุกผลเพื่อเช็คว่า ถ้ากินผลนี้แล้วต้องกินแก้ไขพิษเท่าไหร่ เอาค่าที่แก้มากทุก (ถ้าแก้ไม่ได้ก็ปล่อยเลย)
ลองจาก testcase ที่โจทย์ให้บ้าง
ตัวอย่างที่ 1
[-1] => [1]
00 => {01, w=5}
10 => {01, w=6}
00 => {10, w=7}
11 => {00, w=8}
เริ่ม dijktra จาก 00
00 = 0
pq += {01, w=5}, {10, w=7}
01 = 5
pq += {00, w=5}
10 = 7
pq += {01, w=7+6}
ที่เหลือไปไม่ได้
จากจุดเริ่ม
ผล1. 00=0
ผล2. 10=7
ผล3. 00=0
ผล4. 11=infinity
ต้องกินผลไม้แก้มากสุดคือ 7 ผล
ตัวอย่างที่ 2
[-1] => [1]
110 => {000, w=1}
000 => {100, w=1}
001 => {000, w=1}
010 => {001, w=1}
100 => {010, w=1}
เริ่ม dijktra จาก 000
000 = 0
pq += {100, w=1}
100 = 1
pq += {010, w=1+1=2} กิน apple
pq += {000, w=1+0=1} เพิ่ม subset
010 = 2
pq += {001, w=2+1=3} กิน apple
pq += {000, w=2+0=2} เพิ่ม subset
001 = 3
pq += {000, w=3+1} กิน apple
pq += {000, w=3+0=3} เพิ่ม subset
ที่เหลือไปไม่ได้
จากจุดเริ่ม
ผล1. 110=infinity
ผล2. 000=0
ผล3. 001=3
ผล4. 010=2
ผล5. 100=1
ต้องกินผลไม้แก้มากสุดคือ 3 ผล
ทำ dijjktra บน state 2^k = 2^19 แบบ
แต่ละ state สามารถสร้างเส้นเชื่อมได้ 2 วิธี
- กิน apple มีค่ารวมทั้งหมดไม่เกิน
n <= 80,000แบบ - เพิ่ม subset ในชั้นต่อไปของ bitmask นั้น
O(k)
รวมเป็น O(n + 2^k * k * log(2^k)) = O(n + 2^k * k^2)
แต่ตอนทำจริงยังไงค่าใน priority_queue ก็ไม่เยอะหรอก เพราะว่า ถ้าทำ state ไหนแล้ว state ลูกของมันก็ต้องถูกเติมด้วยเหมือนกัน เช่นถ้าแก้พิษ 01101 ได้ ก็ต้องแก้ { 01100, 01001, 00101, 01000, 00100, 00001, 00000 } ได้ด้วยเช่นกันถ้ายังไม่เคยทำ