Usaco2013
เนื้อหา
USACO 2013 February Contest, Gold
Problem 1: Partitioning the Farm [Brian Dean, 2013]
Source: [1]
ฟาร์มของชาวนาจอห์นแบ่งเป็นช่องตารางกริดขนาด N x N (2 <= N <= 15) ตอนนี้ที่ฟาร์มมีแค่รั้วล้อมภายนอกฟาร์ม แต่วัวสามารถเดินไปมาระหว่างช่องในฟาร์มได้
ชาวนาจอห์นตัดสินใจว่าจะสร้างรั้วเพื่อแบ่งวัวออกเป็นกลุ่ม ๆ เนื่องจากกฎหมายการแบ่งโซน รั้วที่สร้างจะต้องเป็นรั้วในแนวตั้งหรือแนวนอน และมีความยาวจากขอบฟาร์มด้านหนึ่งไปยังขอบอีกด้านหนึ่ง และรั้วจะไม่สามารถสร้างผ่านช่องของตารางกริด ชาวนาจอห์นมีเงินมากพอที่จะสร้างรั้วได้แค่ K รั้วเท่านั้น (1 <= K <= 2N-2)
ชาวนาจอห์นต้องการจะสร้างรั้วเพื่อที่จะทำให้ขนาดของกลุ่มวัวที่แบ่งได้ที่ใหญ่ที่สุด มีขนาดเล็กที่สุด (วัวสองตัวจะอยู่ในกลุ่มเดียวกัน ถ้าวัวสามารถเดินถึงกันได้โดยไม่ต้องผ่านรั้ว) ใช้ข้อมูลของจำนวนวัวในแต่ละช่อง ช่วยชาวนาจอห์นคำนวณหาขนาดของกลุ่มวัวที่ใหญ่ที่สุด เมื่อเขาแบ่งรั้วในรูปแบบที่ดีที่สุดแล้ว
ข้อมูลนำเข้า
- บรรทัด 1: จำนวนเต็มสองจำนวน N และ K
- บรรทัด 2..1+N: แต่ละบรรทัดมีจำนวนเต็ม N จำนวน แทนจำนวนวัวในแต่ละช่องในแถวหนึ่ง ๆ ของฟาร์ม (จำนวนวัวจะมีค่าไม่น้อยกว่า 0 และไม่เกิน 1 000 ตัว ในแต่ละช่อง
ตัวอย่าง input
3 2 1 1 2 1 1 2 2 2 4
ข้อมูลส่งออก
มีบรรทัดเดียว เป็นขนาดของกลุ่มวัวที่ใหญ่ที่สุด ที่น้อยที่สุดที่เป็นไปได้
ตัวอย่าง
4
คำอธิบาย
ชาวนาจอห์นควรจะสร้างรั้วระหว่างคอลัมน์ 2 และ 3, และระหว่างแถวที่ 2 และ 3 ซึ่งจะทำให้มีกลุ่มวัว 4 กลุ่ม กลุ่มละ 4 ตัว
