题目描述

chenzeyu97的家可以看成是一个n*m的矩阵，每块区域都有独一无二的海拔高度h（h>0）！其最大值为n*m。

现在他要选择一个子矩阵摆放一张桌子，在他眼里，这样摆放桌子的美观度为这个子矩阵中所有元素中值的最小值，他想知道，如果他要求摆放桌子的美观度为i，那么可以选择多少种子矩阵呢？

对于所有可能的i值（1≤i≤n*m），你都应该得出其方案数，这样你就能顶替蒟蒻hzwer获得被请客的资格！

题解：http://hzwer.com/4727.html

输入

第1行:两个整数N，M;

接下来N行:每行m个整数，描述一个N*M的矩阵.

30%的数据1≤n,m≤50;

100%的数据1≤n,m≤300.

输出

输出N*M行，每行一个整数，第i行表示美观度i的方案数.

样例输入 Copy

样例输出 Copy

提示

【样例解释】

美观度为1的情况:

在2*3的矩阵中，分别选择如下的子矩阵:选择第1行第3列、选择第1行第2列~第1行第3列、选择第1行第1列~第1行第3列、选择第1行第3列~第2行第3列、选择第1行第2列~第2行第3列、选择第1行第1列~第2行第3列，其美观度均为1，共6种情况；

美观度为2的情况:

在2*3的矩阵中，分别选择如下的子矩阵:选择第1行第1列、选择第1行第1列~第1行第2列、选择第1行第1列~第2行第1列、选择第1行第1列~第2行第2列，共4种情况。

以此类推…

思路

这题是单调栈的题目，但用单调队列就会T，因为如果要用单调队列，就还要去枚举一下滑动窗口的长度，所以就多了一个n，所以就T掉了。
讲一下正解，不用想，一定要去枚举左右区间，l->r.
我们要知道每一个行区间l--->r的最小值，这个可以用l-1---->r 用O(1)转移过来。
现在我们就要在行上去统计答案。
现在原题就变成了如何对一个数列，用O(n)的时间复杂度去求出最小值
此时我们只要知道当前的是A{X}，前一个比他小的值是A[Y]，然后这中间的一堆没用的东西就没用了。因为这里面的都没有对答案造成贡献，所以这区间的就可以不管了
然后具体实现就是如果要把一个点放到单调栈里，只要栈顶的最小值比他大，就将栈顶给这个点，并不断统计答案的影响。
f数组表示当前的往前的最长区间，然后答案就是向前最大的长度*向后最大的长度（乘法原理，我一直以为是公式，然后被机房大佬疯狂嘲讽）
mn里存下预处理好的高度。
然后放到单调栈里，不断的弹，然后就是统计答案了

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const int MAX = ;

 int n, m;

 int a[MAX][MAX], sta[MAX], top, mn[MAX];

 LL f[MAX], ans[MAX * MAX];

 int read()

 {

     char c;

     int num, f = ;

     while (c = getchar(), !isdigit(c))

         if (c == '-')

             f = -;

     num = c - '';

     while (c = getchar(), isdigit(c))

         num = num *  + c - '';

     return f * num;

 }

 void calc()

 {

     int i, j;//手动写一个单调栈，去模拟将一个点放入后的贡献。

     LL sum;

     top = ;

     for (i = ; i <= n; i++)

     {

         f[i] = ;

         sum = ;

         while (top && mn[i] < mn[sta[top]])

         {

             ans[mn[sta[top]]] += f[sta[top]] * sum;

             sum += f[sta[top]];

             f[i] += f[sta[top]];

             top--;

         }

         sta[++top] = i;

     }

     sum = ;

     while (top)

     {

         ans[mn[sta[top]]] += f[sta[top]] * (sum + );

         sum += f[sta[top]];

         top--;

     }

 }

 int main()

 {

     int i, j, k;

     n = read();

     m = read();

     memset(ans, , sizeof(ans));

     memset(f, , sizeof(f));

     for (i = ; i <= n; i++)

         for (j = ; j <= m; j++)

             a[i][j] = read();

     for (i = ; i <= m; i++)

     {

         memset(mn, , sizeof(mn));

         for (j = i; j <= m; j++)

         {

             for (k = ; k <= n; k++)

                 mn[k] = min(mn[k], a[k][j]);//这就是一个简单的预处理，存的就是从l开始的每一个区间的高度

             calc();

         }

     }

     for (i = ; i <= n * m; i++)

         printf("%d\n", ans[i]);

     return ;

 }

巴特西

[校内自测 NOIP模拟题] chenzeyu97要请客(单调栈)

题目描述

输入

输出

样例输入 Copy

样例输出 Copy

提示

思路

最新文章

热门文章