TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3483
  • 题目
  • P3483好线路
    限制 : 时间限制 : 10000 MS   空间限制 : 265536 KB
    问题描述

    nodgd在旅游。现在,nodgd要从城市的西北角走到东南角去。这个城市的道路并不平坦,nodgd希望找出一条相对比较好走的路。
    nodgd事先已经得到了这个城市的地图。地图上这个城市是一个n×m的矩形,nodgd现在站在坐标为(1,1)的位置,需要到达坐标为(n,m)的位置。这张地图上用非负整数标记了每个整数坐标点的海拔,坐标为(x,y)的位置的海拔是ℎ(x,y)。nodgd希望找出一条路线,路线中任意时刻都在向正东或向正南走,而且只在整数坐标点的地方转弯,使得路上经过的n+m−1个整数坐标点的海拔的方差最小。然而万能的nodgd当然知道该怎么走,也当然知道方差最小是多少,只是想顺便考考你。
    假如有𝑘个实数𝑥1,𝑥2,…,𝑥𝑘,则平均值𝑥̅定义为
         x1+x2+...+xk
    𝑥̅=--------------
                 k
    方差σ2定义为
           (x1-𝑥̅)2+(x2-𝑥̅)2+...+(xk-𝑥̅)2
    σ2=----------------------------
                            k
    在本题中为了方便,你只需要求出(n+m−1)2×σ2的最小值即可,众所周知这是个整数。

    输入格式

    //输入文件C.in。
    第一行输入两个整数n,m,表示城市的大小。
    接下来n行,每行m个数,其中第x行第y个数就是ℎ(x,y)。

    输出格式

    //输出文件C.out。
    输出一行一个整数,表示(n+m−1)2×σ2的最小值。

    样例输入

    2 2
    1 2
    3 4

    样例输出

    14

    提示

    【样例解释】
    有两条路1-2-4和1-3-4,方差都等于14/9,所以方差最小值是14/9,输出14。
    【数据范围】
    对于30%的数据,1≤n,m≤10;
    对于50%的数据,1≤n,m≤20;
    对于100%的数据,1≤n,m≤50,0≤ℎ(x,y)≤50。


    来源  by nodgd