最大上升子矩阵(matrix)

背景：

所谓最长上升子矩阵，就是这个矩阵中的任一元素的值都大于它左边、上边的元素的值。如以下子矩阵是一个上升子矩阵：

1 2 3 4

2 3 4 5

4 5 7 9

在给定的一个 n*m 的矩阵中，最大的一个上升子矩阵，要求求出它的面积。

输入格式：

第一行：两个正整数 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

输出样例：

1

数据说明：样例中最大的上升子矩阵是：

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
     
       2 #include
      
        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]
       
        =1;k--) 19                 if (a[i][k]
        
         =1; k--)27             {28                 if (k*(left[i][j]+1)
         
          =i-k+1; l--) 32                     if (ans>left[l][j]+1) ans=left[l][j]+1;33                 if (k*ans
          
           =j-ans+1; l--)35 if (up[i][l]+1
           
            maxx) maxx=ans;39 }40 }41 printf("%d",maxx);42 return 0; 43 }