b172. 雷曼兔
標籤 :
通過比率 : 102人/126人 ( 81% ) [非即時]
評分方式:
Tolerant

最近更新 : 2008-11-09 23:40

內容

        这次,OI山成为了雷曼兔那无尽的冒险传说的新舞台!传说OI山中埋藏着巨大的宝藏,伴随着这个传说的是一个迷题:最瑰丽的舞者将达至精灵世界的彼岸……

        经过仔细推敲,雷曼兔发现这是一个提示宝藏埋藏位置的谜语,在该谜语中指出了一个特定的路径,只有经过了该路径宝藏才会出现,具体情况如下:

        OI山的地势图可以看作一个N*N的数字矩阵,由1-N^2的数字组成(每个数字出现且仅出现一次),这些数字表示每个地点的地势高低。雷曼兔的出发点在最高的山顶处,并且每次雷曼兔可以从其当前所在的位置跳跃到任何一个比当前地点高度低的位置,假设雷曼兔该次跳跃从坐标(x1,y1)跳到了坐标(x2,y2),则这次跳跃的华丽度定义为v=(|x1-x2|+|y1-y2|)^2。而开启宝藏秘密的路径就是从山顶不断跳跃直到山底(高度最低点)的华丽度总和最高的路径,而现在我们想要知道的是这个最高的华丽度总和是多少。

輸入說明

        第一行包括一个整数n(n<=50)表示地图的长宽。

        接下来n行每行包括n个数表示每个地点的高度。

輸出說明

        输出包括一个整数ans,表示从山顶到山底最高华丽度总和。

範例輸入 #1
2
3 2 
1 4
範例輸出 #1
9
測資資訊:
記憶體限制: 512 MB
提示 :
最优路径为4->3->2->1,得分为4+1+4=9。
標籤:
出處:
2008海峽兩岸青少年程式設計競賽

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
32290 dfd8282@gmai ... (fishhh) b172
解題報告
218 2022-09-27 01:23