แคนดี้สูงสุดที่คุณจะได้รับจากกล่องใน C++

สมมติว่าเรามี n กล่อง ที่นี่แต่ละกล่องจะได้รับในรูปแบบเช่น [สถานะ ลูกอม กุญแจ กล่องที่บรรจุ] มีข้อจำกัดบางประการ -

• สถานะ[i]:an คือ 1 เมื่อ box[i] เปิดอยู่ และ 0 เมื่อปิด box[i]

• candies[i]:คือจำนวนลูกกวาดในกล่อง[i].

• keys[i]:เป็นอาร์เรย์ที่มีดัชนีของกล่องที่เราเปิดได้ด้วยคีย์ในกล่อง[i]

• มีกล่อง[i]:อาร์เรย์ประกอบด้วยดัชนีของกล่องที่พบใน box[i].

เราจะเริ่มต้นด้วยกล่องบางกล่องที่กำหนดในอาร์เรย์ initialBoxes เราสามารถนำลูกอมทั้งหมดในกล่องที่เปิดอยู่และเราสามารถใช้กุญแจในการเปิดกล่องใหม่ได้ และเรายังสามารถใช้กล่องที่เราพบในนั้นได้อีกด้วย

เราต้องหาจำนวนลูกอมสูงสุดที่เราจะได้รับตามกฎเหล่านี้ตามที่กล่าวไว้ข้างต้น

ดังนั้น หากอินพุตเป็นเหมือนสถานะ =[1,0,1,0] ลูกอม =[8,6,5,101] และคีย์ =[[], [], [1], []], มีกล่อง =[ [1,2],[3],[],[]], initialBoxes =[0], ผลลัพธ์จะเป็น 19 เนื่องจากเราจะได้รับกล่อง 0 ในตอนแรก เราจะพบลูกอม 8 อันในนั้นและกล่อง 1 และ 2 กล่อง 1 ไม่ได้เปิดและเราไม่มีกุญแจสำหรับมันดังนั้นเราจะเปิดกล่อง 2 เราจะพบ 5 ลูกอมและกุญแจไปยังกล่อง 1 ในกล่อง 2 ในกล่อง 1 คุณจะพบ 6 ลูกอมและ กล่อง 3 แต่เราจะไม่พบกุญแจไปยังกล่อง 3 ดังนั้นกล่อง 3 จะยังคงปิดอยู่ จำนวนลูกอมที่เก็บได้ =8 + 5 + 6 =19 ลูก

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ตอบ :=0

• กำหนดหนึ่งคิว q

• กำหนดชุดที่เข้าชม เปิด hasKey

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ ib ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • x :=ib[i]

  • ใส่ x เข้าไป

  • ถ้า st[x] เหมือนกับ 1 แล้ว −

    • ans :=ans + cnt[x]

    • ใส่ x ลงในช่องที่เปิดอยู่

    • แทรก x ลงใน q

• ในขณะที่ (ไม่ใช่ q ว่างเปล่า) ทำ -

  • curr :=องค์ประกอบแรกของ q

  • ลบองค์ประกอบออกจาก q

  • สำหรับการเริ่มต้น i :=0 เมื่อ i

    • x :=k[curr, i]

    • ใส่ x ลงใน hasKey

    • ถ้า x ไม่ได้เปิดอยู่และ x ไม่ได้เปิดอยู่ −

      • ans :=ans + cnt[x]

      • แทรก x ลงใน q

      • ใส่ x ลงในช่องที่เปิดอยู่

  • สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของ cb[curr] อัปเดต (เพิ่ม i โดย 1) ทำ -

    • x :=cb[curr, i]

    • ใส่ x เข้าไป

    • ถ้า x ไม่อยู่ใน open และ x อยู่ใน hasKey หรือ st[x] เหมือนกับ 1) ดังนั้น −

      • ใส่ x ลงในช่องที่เปิดอยู่

      • ans :=ans + cnt[x]

      • แทรก x ลงใน q

• กลับมาอีกครั้ง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include ใช้เนมสเปซ std;class Solution { public:int maxCandies(vector&st, vector&cnt, vector>&k, vector>&cb, vector&ib) { int ans =0; คิว q; set เยี่ยมชม; set เปิด; set hasKey; สำหรับ (int i =0; i  v ={1,0,1,0}, v1 ={8,6,5,101}, v2 ={0}; เวกเตอร์<เวกเตอร์> v3 ={{},{},{1},{}}, v4 ={{1,2},{3},{0},{}}; ศาล <<(ob.maxCandies(v, v1, v3, v4, v2));}

อินพุต

ผลลัพธ์

19