【tyvj1466】最美妙的矩阵

2014年3月3日1,8110

背景 Background

Candy的生日即将到来,飘飘乎居士希望找到一个最美妙的矩阵送个Candy作为礼物

描述 Description

飘飘乎居士从Pink处得知最美妙的矩阵满足三个条件:首先,它的长和宽都必须和矩阵的边界平行(也就是不可以出现斜的矩阵);第二:子矩阵横竖都要满足单调递增(可以相等,也就是对于每一个最优子矩阵的元素都要满足a[i][j]>=a[i-1][j] and a[i][j]>=a[i][j-1],其中a[i][j]表示矩阵第i行第j列的数字);第三:最优矩阵是在满足上述两个条件中面积最大的矩阵。

输入格式 InputFormat

第一行,两个正整数n,m
接下来n行,每行m个数字,构成一个n*m的矩阵

输出格式 OutputFormat

一行,代表最优矩阵的面积

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

最优子矩阵为
2 4 4
4 4 4
该矩阵满足横竖都单调递增,并且是所有满足条件中面积最大的。其中矩阵长为3宽为2,面积为6,也就是最后的答案。
对于30%的数据  0<n m<=50
对于100%的数据 0<n m<=200
对于所有数据 a[i][j]<=20000000

代码
时间及空间复杂度 题解
时间复杂度:O(n^6)

空间复杂度:O(n^2)

方法一:枚举子矩阵的每一个左上角坐标和右下角坐标,在逐个检查枚举的矩阵是否符合单调特性。预期得分30
时间复杂度:O(N^3)

空间复杂度:O(N^3)

方法二:预处理column[i][j]以及can[i][j][k]数组。

 

其中column[i][j]表示坐标为i j的点能向上单调递减的长度。则

column[i][j]={column[i-1][j]+1(a[i][j]>=a[i-1][j]),column[i][j]=1}

 

用can[i][j][k]表示从第i行到第j行中的第k列能否接道第i行到第j行的k-1列中,则关于can[i][j][k]=true的条件为

(can[i][j-1][k])and(column[j][k]>=j-i+1)and(a[j][k]>=a[j][k-1])and(coulumn[j][k-1]>=j-i+1。

 

接下来用f[i][j][k]表示从第i行到第j行中,第k列的最大子矩阵

F[i][j][k]=f[i][j][k-1]+j-i+1   (can[i][j][k]=true)

=j-i+1 (can[i][j][k]=false and column[j][k]>=j-i+1)

=0 (else)

预期得分100