Usaco2011

USACO OPEN 2011

Problem 1: Mowing the Lawn [Neal Wu, 2008]

หลังจากที่ชาวนาจอห์นชนะการประกวดสนามหญ้าเมื่อปีก่อน เขาก็เริ่มขี้เกียจ เขาไม่ได้ตัดหญ้ามาตั้งแต่ตอนนั้น ซึ่งทำให้สนามหญ้าของเขารกมาก อย่างไรก็ตาม การประกวดกำลังจะเริ่มต้นเร็ว ๆ นี้ และ FJ ต้องการจะจัดการกับสนามหญ้าของเขาให้เรียบร้อยเพื่อที่จะได้พร้อมเข้าประกวด

FJ จะใช้วัว N ตัว (1 <= N <= 100,000) ที่เรียงต่อกันเป็นเส้น โดยมีหมายเลขตั้งแต่ 1 ถึง N มาช่วยจัดการกับสนามหญ้า วัวบางตัวจะมีประสิทธิภาพมากกว่าวัวตัวอื่น วันตัวที่ i มีประสิทธิภาพ E_i หน่วย (0 <= E_i <= 1,000,000,000)

FJ สังเกตว่าวัวตัวที่อยู่ติดกันมักรู้จักวัวตัวอื่น เขายังทราบว่าถ้าเขาเลือกวัวมากกว่า K ตัวติดกัน (1 <= K <= N) วัวเหล่านั้นจะไม่ทำงานและเริ่มจัดงานเลี้ยงแทน ดังนั้น FJ จึงต้องการให้คุณช่วยเลือกวัว ให้ได้ผลรวมของประสิทธิภาพมากที่สุด โดยที่ไม่เลือกวัว K ตัวติดกันเลย