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 ตัวติดกันเลย

Full task description (mirrored from [1])

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

After winning the annual town competition for best lawn a year ago,
Farmer John has grown lazy; he has not mowed the lawn since then
and thus his lawn has become unruly. However, the competition is
once again coming soon, and FJ would like to get his lawn into
tiptop shape so that he can claim the title.

Unfortunately, FJ has realized that his lawn is so unkempt that he
will need to get some of his N (1 <= N <= 100,000) cows, who are
lined up in a row and conveniently numbered 1..N, to help him. Some
cows are more efficient than others at mowing the lawn; cow i has
efficiency E_i (0 <= E_i <= 1,000,000,000).

FJ has noticed that cows near each other in line often know each
other well; he has also discovered that if he chooses more than K
(1 <= K <= N) consecutive (adjacent) cows to help him, they will
ignore the lawn and start a party instead. Thus, FJ needs you to
assist him: determine the largest total cow efficiency FJ can obtain
without choosing more than K consecutive cows.

PROBLEM NAME: mowlawn

INPUT FORMAT:

* Line 1: Two space-separated integers: N and K

* Lines 2..N+1: Line i+1 contains the single integer: E_i

SAMPLE INPUT (file mowlawn.in):

5 2
1
2
3
4
5

INPUT DETAILS:

FJ has 5 cows whose efficiencies are 1, 2, 3, 4, and 5, in that
order. He wants to choose some of the cows such that their total
efficiency is maximized, but he cannot choose more than 2 consecutive
cows.

OUTPUT FORMAT:

* Line 1: A single integer that is the best total efficiency FJ can
        obtain.

SAMPLE OUTPUT (file mowlawn.out):

12

OUTPUT DETAILS:

FJ chooses all cows but the third. The total efficiency of the cows is thus
1 + 2 + 4 + 5 = 12.

Problem 2: Odd degrees [Traditional, 2011]

เหล่าวัวถูกบุกรุก! อาณาจักรของพวกเขาประกอบไปด้วยเมือง N เมือง (1 <= N <= 50,000) ที่เชื่อมต่อกันด้วยเส้นทาง M เส้น (1 <= M <= 100,000) ที่ไม่มีทิศทาง โดยสำหรับเส้นทางเส้นที่ i จะเชื่อมระหว่างเมือง A_i และ B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i; และไม่มีเส้นทางที่ซ้ำกัน) อย่างไรก็ตามอาณาจักรไม่จำเป็นต้องเชื่อมต่อกันทั้งหมด อาจจะมีเมืองบางกลุ่มที่ไม่สามารถเดินทางไปถึงเมืองอีกบางกลุ่มได้ผ่านทางเส้นทาง

เหล่าวัวทราบว่าผู้บุกรุกต้องการเก็บข้อมูลของเส้นทางทุกเส้นในอาณาจักร พวกวัวจึงต้องการจะปิดเส้นทางบางเส้นเพื่อทำให้ผู้บุกรุกทำงานได้ลำบาก

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

พิจารณาตัวอย่าง

1---2
 \ /
  3---4

ถ้าเราเก็บเส้นทาง 1-3, 2-3, และ 3-4, และลบเส้นทาง 1-2, เมือง 1, 2, 4 เป็นเป็นจุดปลายของเส้นทางแค่หนึ่งเส้น และเมืองที่ 3 จะมีจุดปลายของถนนสามเส้น ดังรูป

1   2
 \ /
  3---4

Problem 3: Soldering [Michael Cohen, 2011]

เหล่าวัวกำลังเล่นกับสายไฟ พวกเขาเริ่มรู้จักเทคนิคที่เรียกว่าการบัคกรี (soldering) ซึ่งเป็นการเชื่อมสายสองเส้นเข้าด้วยกัน โดยการนำจุดปลายของสายหนึ่ง เชื่อมเข้ากับบางจุดในสายอีกเส้นหนึ่ง (การบัคกรีจุดปลายสองจุดเชื่อมกันนั้นทำไม่ได้) อาจจะมีการบัคกรีเชื่อมสายหลายสายเข้าที่จุดเดียวกัน

เหล่าวัวมีแผนการที่จะสร้างโครงสร้างมหัศจรรย์ (Amazing Structure) โครงสร้างดังกล่าวมีลักษณะเป็นกราฟที่มี N โหนด (1 <= N <= 50,000) และมีเส้นเชื่อม N-1 เส้นที่แต่ละเส้นมีความยาว 1 หน่วย โดยรับประกันว่าทุก ๆ คู่ของโหนดนั้นจะสามารถเชื่อมถึงกันได้ แต่ละเส้นจะอธิบายโดยใช้คู่ของจำนวนเต็ม A และ B (1 <= A <= N; 1 <= B <= N; A != B)

เหล่าวัวสามารถซื้อสายไฟจากร้านค้า แต่สายไฟยิ่งยาวยิ่งแพง กล่าวคือ วัวสามารถซื้อสายไฟที่ความยาว L โดยจ่ายเงิน L*L หน่วย แต่วัวไม่สามารถตัดหรือเชื่อมสายเข้าด้วยกันได้

ด้วยแผนการดังกล่าว วัวต้องการจะบัคกรีสายเข้าด้วยกัน เพื่อที่จะสร้างโครงสร้างมหัศจรรย์ ช่วยหาวิธีการที่ประหยัดเงินมากที่สุด

ข้อมูลทดสอบ 50% จะมี N <= 2,000

มี partial feedback สำหรับการส่ง 50 ครั้งแรก