首页 > 代码库 > 最大上升子矩阵
最大上升子矩阵
最大上升子矩阵(matrix)
背景：
所谓最长上升子矩阵，就是这个矩阵中的任一元素的值都大于它左边、上边的元素的值。如以下子矩阵是一个上升子矩阵：
1 2 3 4
2 3 4 5
4 5 7 9
在给定的一个 n*m 的矩阵（LJJ 的班级）中，最大的一个上升子矩阵，于是他找到你来帮忙，要求求出它的面积。
输入格式：
第一行：两个正整数 n,m，分别表示行数和列数。
第二行到第 n+1 行，每行 m 个整数（可能是负）
输出格式：
第一行：最大上升子矩阵的面积
输入样例：
5 5
3 1 2 5 7
1 2 3 4 6
2 4 5 6 9
1 5 7 9 7
3 6 8 10 1
输出样例：
12
数据说明：样例中最大的上升子矩阵是：
2 3 4
4 5 6
5 7 9
6 8 10
面积是 12
数据范围：
对于 50%的数据，1<n,m<=100，
对于 100%的数据，1<n,m<=1000，-10000<a[i][j]<10000，大多数数据
随机生成，有少量极端数据。
洛谷水题，dp O(n^4)+剪枝即可
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 int n,m,a[1001][1001],left[1001][1001],up[1001][1001],ans,maxx; 5 6 int main() 7 { 8 freopen("matrix.in","r",stdin); 9 freopen("matrix.out","w",stdout);10 scanf("%d%d",&n,&m);11 for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) scanf("%d",&a[i][j]);12 for (int i=1; i<=n; i++)13 for (int j=1;j<=m;j++)14 {15 for (int k=i-1;k>=1;k--) 16 if (a[k][j]<a[k+1][j]) up[i][j]++; 17 else break;18 for (int k=j-1;k>=1;k--) 19 if (a[i][k]<a[i][k+1]) left[i][j]++; 20 else break;21 }22 maxx=0;23 for (int i=1; i<=n; i++)24 for (int j=1; j<=m; j++)25 {26 for (int k=up[i][j]+1; k>=1; k--)27 {28 if (k*(left[i][j]+1)<maxx) break;29 int l;30 ans=left[i][j]+1;31 for (l=i; l>=i-k+1; l--) 32 if (ans>left[l][j]+1) ans=left[l][j]+1;33 if (k*ans<maxx) continue;34 for (l=j; l>=j-ans+1; l--)35 if (up[i][l]+1<k) break;36 if (j-l<ans) ans=j-l;37 ans=ans*k;38 if (ans>maxx) maxx=ans;39 }40 }41 printf("%d",maxx);42 return 0; 43 }
最大上升子矩阵
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。