【NOIP模拟赛】[hdu5492]小奇的矩阵

2015年10月5日2,1826

【题目背景】

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

【问题描述】

给定一个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

 

  • cyy4892015年10月7日 上午10:42 回复

    黄学长,请问
    设我们枚举的SN比真实的Ai和小E,E是任意实数
    很容易证明∑(Ai-Aavg)^2<∑(Ai-av+E)^2
    怎么证明?

    #1  
    • hzwer2015年10月7日 下午7:38 回复
      admin

      全部展开,消完一边会剩下NE^2

      #11
  • cyy4892015年10月10日 下午10:25 回复

    多谢回答!

    #2  
  • 魔法炮2015年10月12日 下午11:12 回复

    求发NOIP2015游记!

    #3