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 < 10100% ของชุดทดสอบทั้งหมด 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 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้