【子矩阵】【高效算法设计】

.子矩阵

小A 有一个N×M 的矩阵，矩阵中1~N*M 这(N*M)个整数均出现过一次。现在小A 在这个矩阵内选择一个子矩阵，其权值等于这个子矩阵中的所有数的最小值。小A 想知道，如果他选择的子矩阵的权值为i(1<=i<=N×M)，那么他选择的子矩阵可能有多少种？小A 希望知道所有可能的i 值对应的结果，但是这些结果太多了，他算不了，因此他向你求助。
输入格式
第一行，两个整数N, M。
接下来的N 行，每行M 个整数，表示矩阵中的元素。
输出格式
N×M 行，每行一个整数，其中第i 行的整数表示如果小A 选择的子矩阵权
值为i，他选择的子矩阵的种类数。

输入样例
2 3
2 5 1
6 3 4

输出样例
6

数据范围
对于30%的数据，1<=N, M<=50；
对于全部的数据，1<=N, M<=300。

Solution:

首先我觉得关于这种矩阵的题还是很有必要总结一下的。这是第一道典型：寻找关于某些满足条件矩阵的信息(矩阵当然是连续的)

我们先考虑怎么暴力。

枚举所有的子矩阵：即枚举四个边界，然后查找最小值复杂度达到了惊人的

O（N⁶）。

那么考虑如何优化这么暴力的枚举方法

① 枚举的条件太多时，可以考虑部分枚举：参见高效算法设计。那么在这道题中，我们可以考虑只枚举上下边界，枚举完一个上界和下界后。我们对在这之间的所有子矩阵处理。

② 如何处理：对于上下边界之间的每一列，我们可以求出该列中的最小值。这个可以预处理得到。复杂度N³（枚举每一个整列需要N*N）然后YZ大神说可以用RMQ 快速N*logN搞出来。

③ 然后。我们考虑每一列的最小值可以最多向右向左扩展的长度。所谓扩展的意思是指，当前最小值能影响的最远的地方。

示意一下。

| | | | | |

————————————————————————————-————

1 4 3 6 7 5 2

下面表示该列的最小值。那么考虑3

向左可以扩展到 4(位置2) 向右可以扩展到 5（位置6）

那么记录 L[3]=2R[3]==6

那么L 到R 之间包含了 3 这一列的所有矩阵的最小值都是3！

那么一共有多少个矩阵呢答案是 (K-L+1)*(R-K+1) K就是当前位置

用一个单调堆来维护整个区间，就可以高效的算出每个点最远可以拓展的点。

假设我们先算可以向右拓展多远。

单调栈中有

1入栈 1

4入栈 1 4

3入栈 1 3 （弹出了4）说明4只能扩展到3 这个位置

6入栈 1 3 6

7入栈 1 3 6 7

5入栈 1 3 5 （弹出了6 7,）说明6 7 只能扩展到 5 这个位置

2入栈 1 2 （弹出了3 5）说明 3 5只能扩展到 2所在的位置、

然后栈里面剩下的树都可以扩展到最右边。

左边就不说了。

由此可以的出答案。

 
  #include<cstdio>
 
 
  #include<iostream>
 
 
  #include<cstring>
 
 
  #include<stack>
 
 
  using 
  namespace 
  std
  ;
 
 
  const 
  int 
  maxn
  =
  305
  ,
  inf
  =
  0x3f3f3f3f
  ;
 
 
  int 
  n
  ,
  m
  ,
  s
  [
  maxn
  ][
  maxn
  ],
  miny
  [
  maxn
  ],
  ans
  [
  maxn
  *
  maxn
  ],
  L
  [
  maxn
  ],
  R
  [
  maxn
  ];
 
 
  stack
  <
  int
  >
  q
  ;
 
 
  inline 
  void 
  _read
  (
  int 
  &
  x
  ){ 
 
     
  char 
  t
  =
  getchar
  ();
  bool 
  sign
  =
  true
  ; 
 
     
  while
  (
  t
  <
  '0'
  ||
  t
  >
  '9'
  ) 
 
     
  {
  if
  (
  t
  ==
  '-'
  )
  sign
  =
  false
  ;
  t
  =
  getchar
  ();} 
 
     
  for
  (
  x
  =
  0
  ;
  t
  >=
  '0'
  &&
  t
  <=
  '9'
  ;
  t
  =
  getchar
  ())
  x
  =
  x
  *
  10
  +
  t
  -
  '0'
  ; 
 
     
  if
  (
  !
  sign
  )
  x
  =-
  x
  ; 
 
 
  } 
 
 
  int 
  main
  (){
 
 	
  _read
  (
  n
  );
  _read
  (
  m
  );
 
 	
  int 
  i
  ,
  j
  ,
  k
  ;
 
 	
  for
  (
  i
  =
  1
  ;
  i
  <=
  n
  ;
  i
  ++
  )
 
 		
  for
  (
  j
  =
  1
  ;
  j
  <=
  m
  ;
  j
  ++
  )
  _read
  (
  s
  [
  i
  ][
  j
  ]);
 
 	
  for
  (
  i
  =
  1
  ;
  i
  <=
  n
  ;
  i
  ++
  ){
 
 		
  memset
  (
  miny
  ,
  inf
  ,
  sizeof
  (
  miny
  ));
 
 		
  for
  (
  j
  =
  i
  ;
  j
  <=
  n
  ;
  j
  ++
  ){
 
 			
  for
  (
  k
  =
  1
  ;
  k
  <=
  m
  ;
  k
  ++
  )
  miny
  [
  k
  ]
  =
  min
  (
  miny
  [
  k
  ],
  s
  [
  j
  ][
  k
  ]);
 
 			
  for
  (
  k
  =
  1
  ;
  k
  <=
  m
  ;
  k
  ++
  ){
 
 				
  while
  (
  q
  .
  size
  ()
  &&
  miny
  [
  k
  ]
  <
  miny
  [
  q
  .
  top
  ()]){
 
 					
  R
  [
  q
  .
  top
  ()]
  =
  k
  -
  1
  ;
 
 					
  q
  .
  pop
  ();
 
 				
  }
 
 				
  q
  .
  push
  (
  k
  );
 
 			
  }
 
 			
  while
  (
  q
  .
  size
  ()){
 
 				
  R
  [
  q
  .
  top
  ()]
  =
  m
  ;
 
 				
  q
  .
  pop
  ();
 
 			
  }
 
 			
  for
  (
  k
  =
  m
  ;
  k
  ;
  k
  --
  ){
 
 				
  while
  (
  q
  .
  size
  ()
  &&
  miny
  [
  k
  ]
  <
  miny
  [
  q
  .
  top
  ()]){
 
 					
  L
  [
  q
  .
  top
  ()]
  =
  k
  +
  1
  ;
 
 					
  q
  .
  pop
  ();
 
 				
  }
 
 				
  q
  .
  push
  (
  k
  );
 
 			
  }
 
 			
  while
  (
  q
  .
  size
  ()){
 
 				
  L
  [
  q
  .
  top
  ()]
  =
  1
  ;
 
 				
  q
  .
  pop
  ();
 
 			
  }
 
 			
  for
  (
  k
  =
  1
  ;
  k
  <=
  m
  ;
  k
  ++
  )
 
 				
  ans
  [
  miny
  [
  k
  ]]
  +=
  (
  R
  [
  k
  ]
  -
  k
  +
  1
  )
  *
  (
  k
  +
  1
  -
  L
  [
  k
  ]);
 
 		
  }
 
 	
  }
 
 	
  for
  (
  i
  =
  1
  ;
  i
  <=
  n
  *
  m
  ;
  i
  ++
  )
 
 		
  printf
  (
  "%d
  \n
  "
  ,
  ans
  [
  i
  ]);
 
 
  }

原文链接：https://blog.csdn.net/Star_Weeper/article/details/53104356