NKOJ 3861 子矩阵（矩阵dp+单调队列）

发表于 |
字数统计: 628字 | 阅读时长 ≈ 3min

P3861子矩阵

问题描述

小 A 有一个 N×M 的矩阵，矩阵中 1~NM 这(NM)个整数均出现过一次。 现在小 A 在这个矩阵内选择一个子矩阵，其权值等于这个子矩阵中的所有数的最 小值。小 A 想知道，如果他选择的子矩阵的权值为 i(1<=i<=N×M)，那么他选择 的子矩阵可能有多少种？小 A 希望知道所有可能的 i 值对应的结果，但是这些结 果太多了，他算不了，因此他向你求助。

输入格式

第一行，两个整数 N,M。
接下来的 N 行，每行 M 个整数，表示矩阵中的元素。

输出格式

N×M 行，每行一个整数，其中第 i 行的整数表示如果小 A 选择的子矩阵权 值为 i，他选择的子矩阵的种类数。

数据范围

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

注意到处理矩阵问题的基本套路，先考虑一维的情况，那么显然变成了单调队列的模板题，即找到左边第一个小于它的数，和右边第一个小于它的数，然后乘一下就是矩阵数

那么处理二维的情况时，枚举上下边界，将矩阵每一列压成一个数，就是这一列最小的一个数，然后仍然变成了单调队列的模板题。复杂度$O(n^2m)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stack>
#define N 305
using namespace std;
stack<int>Q;
int n,m,map[N][N],Min[N][N][N],L[N],R[N];
long long Ans[N*N];
int main()
{
	int i,j,k,p,t;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)scanf("%d",&map[i][j]);
	for(k=1;k<=n;k++)
	for(i=1;i<=m;i++)
	{
	   	t=map[k][i];
	   	for(j=i;j<=m;j++)
	    {
	       	if(map[k][j]<t)t=map[k][j];
	       	Min[k][i][j]=t;
       	}
	}
	for(i=1;i<=m;i++)
	for(j=i;j<=m;j++)
	{
		for(k=1;k<=n+1;k++)
		{
			while(Q.size()&&Min[Q.top()][i][j]>Min[k][i][j])R[Q.top()]=k,Q.pop();
			Q.push(k);
		}
		for(k=n;k>=0;k--)
		{
			while(Q.size()&&Min[Q.top()][i][j]>Min[k][i][j])L[Q.top()]=k,Q.pop();
			Q.push(k);
		}
		Q.pop();
		for(k=1;k<=n;k++)Ans[Min[k][i][j]]+=(L[k]-k)*(k-R[k]);
	}
	for(i=1;i<=n*m;i++)printf("%lld\n",Ans[i]);
}