1114 : กระโดดสูง (HighJ)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)

       คุณเล่นเกมกระโดดในตารางขนาด n คูณ n ตารางหนึ่ง
            ตอนแรกคุณอยู่ที่ช่อง
(n,n) และคุณต้องการเดินทางไปยังช่อง (1,1) โดยการกระโดดหลายๆครั้ง
            คุณสามารถกระโดดจากช่อง
(r,c) ใดๆ ไปยังช่อง (r’,c’) ได้ ก็ต่อเมื่อ r+c > r’+c’เท่านั้น โดยคุณจะเสียพลังงานกระโดดไปทั้งสิ้น          W[ r+c ][ r’+c’ ]

            จงเขียนโปรแกรมเพื่อหาพลังงานที่น้อยที่สุดที่จะต้องใช้ในการกระโดดจาก (n,n) ไปยัง (1,1)

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนนับ n แทนจำนวนแถวและคอลัมน์ของตาราง ( 2 < n < 300 )
บรรทัดที่ 2 ถึง 1+2n จะแสดงถึงตาราง W โดยบรรทัดที่ 1+i จะมีจำนวนนับ 2n จำนวน ซึ่งจำนวนนับที่ j ของบรรทัดที่ 1+i จะแสดงค่าของ  W[ i ][ j ]  ( 1 < W[ i ][ j ] < 10 000 )

ข้อมูลส่งออก

บรรทัดแรกและบรรทัดเดียวแสดงค่าพลังงานที่น้อยที่สุดที่จะต้องใช้ในการกระโดดจาก (n,n) ไปยัง (1,1)

            Note สังเกตได้ว่า ค่าของ W[ i ][ j ] ที่ i < j หรือ i = 1 หรือ j = 1 จะไม่สามารถนำมาคำนวณพลังงานการกระโดดได้ในกรณีใดๆทั้งสิ้น

หมายเหตุ

          50% ของชุดทดสอบทั้งหมด n < 10
            100% ของชุดทดสอบทั้งหมด n < 300

โจทย์โดย : สรวิทย์  สุริยกาญจน์ ( PS.int ) และแนวคิดจากค่าย สสวท. ค่ายที่ 2 ระยะ 2 ประจำปี 2554

ที่มา : ศูนย์ สอวน. โรงเรียนมหิดลวิทยานุสรณ์



ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 
0 1 3 0 0 0 0 0 0 0 
0 2 5 1 0 0 0 0 0 0 
0 8 4 2 2 0 0 0 0 0 
0 8 3 1 3 2 0 0 0 0 
0 9 4 1 6 6 1 0 0 0 
0 20 4 9 8 7 6 1 0 0 
0 20 14 18 15 1 1 3 2 0 
3
5
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 14 0 0 0 0 0 0 0 0 
0 30 15 0 0 0 0 0 0 0 
0 41 21 13 0 0 0 0 0 0 
0 51 42 22 11 0 0 0 0 0 
0 75 58 34 28 12 0 0 0 0 
0 67 71 44 37 23 14 0 0 0 
0 95 77 51 41 44 28 15 0 0 
0 96 94 66 72 41 37 30 11 0
87

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 20 ผู้เยี่ยมชมและ 0 สมาชิก (5 บอท)