「题目背景」

小奇总是在数学课上思考奇怪的问题。

「问题描述」

给定一个n*m的矩阵，矩阵中的每个元素aij为正整数。

接下来规定

1.合法的路径初始从矩阵左上角出发，每次只能向右或向下走，终点为右下角。

2.路径经过的n+m-1个格子中的元素为A1,A2…A(n+m-1)，Aavg为Ai的平均数，路径的V值为(n+m-1)*∑(Ai-Aavg) ^2

(1<=i<=n+m-1)

求V值最小的合法路径，输出V值即可，有多组测试数据。

「输入格式」

第一行包含一个正整数T，表示数据组数。

对于每组数据：

第一行包含两个正整数n和m，表示矩阵的行数和列数。
接下来n行，每行m个正整数aij，描述这个矩阵。

「输出格式」

对于每次询问，输出一行一个整数表示要求的结果

「样例输入」

1

2 2

1 2

3 4

「样例输出」

14

「数据范围」

对于30%的数据 n<=10，m<=10

有另外40%的数据 n<=15 m<=15，矩阵中的元素不大于5

对于100%的数据 T<=5，n<=30，m<=30，矩阵中的元素不大于30

题解

对于30%的数据，把所有的路径深搜出来取最优，复杂度是T*C(2n,n)*n

这道题乍一看像是dp，但是问题在于因为求的是方差与平均数有关，每一步的代价似乎不能直接得出

对于另外40%的数据，我们发现路径Ai和SN不超过120，考虑枚举SN，平均值为av=SN/N（N=n+m-1），那我们就能得到每一步的代价，但是要保证求的路径符合Ai和为SN，设计f(s,i,j)表示到（i,j），和为s的最小代价

f(s,i,j)=min{f(s-a[i][j],i,j-1),f(s-a[i][j],i-1,j)}+(av-a[i][j])^2

复杂度是T*SN^2*n^2

事实上，路径Ai和不等于SN也无所谓，因为对于一条路径，只有我们枚举的SN等于路径Ai和时，这条路径的方差才最小

设我们枚举的SN比真实的Ai和ε，ε是任意实数

很容易证明∑(Ai-av)^2<∑(Ai-av+ε)^2（全部展开）

所以直接去掉dp的第一维，复杂度是T*SN*n^2,可以通过100%的数据

还有另外一种思路，把求方差的式子展开

得到N*∑(Ai^2)-SN^2，设计f(s,i,j)表示到（i,j），和为s的最小的N*∑(Ai^2)，最后枚举s取f(s,i,j)-s^2的最小值，复杂度也是T*SN*n^2

深搜

正解1

正解2