Weighted Interval Scheduling

[bearno1]

statement

มีของ N ชิ้นเรียงกันเป็นเส้นตรง (กำกับด้วยนเลขหมายเลข 0 ถึง n-1 จากซ้ายไปขวา) ของชิ้นที่ I มีชนิด Ai ต้องการให้ของชนิดเดียวกันอยู่ติดกันทั้งหมด สามารถนำของชิ้นใดก็ได้ออกอย่างมาก X ชิ้น (X<3) หลังจากนั้นสามารถเลือกของมาชนิดมาหนึ่งชนิดแล้วเอาของชนิดนั้นออกทั้งหมด(ทำกี่ครั้งก็ได้) จะต้องเอาของออกน้อยที่สุดกี่ชิ้น

concept

Weighted Interval Scheduling (DP)

[bearno1]

ผมลองคิดดูใหม่แล้วขอเปลี่ยนจาก สามารถนำของชิ้นใดก็ได้ออกอย่างมาก X ชิ้น (X<3) สามารถนำของชิ้นใดก็ได้ออกอย่างมาก X ชิ้น (X<1)

+อาจเปลี่ยนให้ยากขึ้นนิดหน่อยด้วยการเปลี่ยนจากสามารถนำของชิ้นใดก็ได้ออกอย่างมาก X ชิ้น เป็นสามารถเปลี่ยนชนิดของของโดยเปลี่ยนได้ไม่เกิน X ชิ้น (X<1)

[peppapighs]

• X = 1, N <= 20, O(N * 2 ^ N)
• X = 0, แต่ละ A_i มีไม่เกิน 2 ตำแหน่ง (hint ของ interval scheduling)
• X = 0, weighted scheduling
• X = 1, มองเป็น interval แยกออกมาจาก array
• X <= 2, DP แล้วลองดูว่าแต่ละตัวเป็นขอบขวาได้หรือไม่