#P871. 【TYVJ1466】最美妙的子矩阵
【TYVJ1466】最美妙的子矩阵
【问题描述】
candy的生日即将到来,飘飘乎居士希望找到一个最美妙的矩阵送个candy作为礼物, 飘飘乎居士从Pink处得知最美妙的矩阵满足三个条件:首先,它的长和宽都必须和矩阵的边界平行(也就是不可以出现斜的矩阵);第二:子矩阵横竖都要满足单调递增(可以相等,也就是对于每一个最优子矩阵的元素都要满足a[i][j]>=a[i-1][j] and a[i][j]>=a[i][j-1],其中a[i][j]表示矩阵第i行第j列的数字);第三:最优矩阵是在满足上述两个条件中面积最大的矩阵。
【输入格式】
第一行,两个正整数n,m
接下来n行,每行m个数字,构成一个n*m的矩阵
【输出格式】
一行,代表最优矩阵的面积
【输入样例】
3 4 2 4 4 4 4 4 4 2 3 4 2 5
【输出样例】
6
【样例说明】
最优子矩阵为
2 4 4
4 4 4
该矩阵满足横竖都单调递增,并且是所有满足条件中面积最大的。其中矩阵长为3宽为2,面积为6,也就是最后的答案。
【数据规模】
对于30%的数据 0<n m<=50
对于100%的数据 0<n m<=200
对于所有数据 a[i][j]<=20000000