**題意:**給你一個數字矩陣,讓你找一個子矩陣,使其滿足每一列是非遞減的,輸出最大的子矩陣的面積。
題解:
- 我們根據每一列進行非遞減的dp,得到dp是以目前點為結尾的最大非降子序列。
-
然後根據我藍書中一道單調棧的題(傳送門),我們可以将每一行的dp當做矩形的高,矩形的寬為1,直接單調棧即可完成計算
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const int N = 2e3 + 50;
int dp1[N][N];
int a[N][N];
int n, m;
int s[N], w[N];
int solve()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
dp1[i][j] = 0;
scanf("%d", &a[i][j]);
}
for (int i = 1; i <= n; i++)
dp1[i][m + 1] = 0;
for (int j = 1; j <= m; j++)
for (int i = 1; i <= n; i++)
{
if (a[i][j] >= a[i - 1][j])
{
dp1[i][j] = dp1[i - 1][j] + 1;
}
else
dp1[i][j] = 1;
}
int ans = 0;
int p = 0;
for (int i = 1; i <= n; i++)
{
p = 0;
for (int j = 1; j <= m + 1; j++)
{
if (dp1[i][j] > s[p])
{
s[++p] = dp1[i][j];
w[p] = 1;
}
else
{
int width = 0;
while (s[p] > dp1[i][j])
{
width += w[p];
ans = max(ans, width * s[p]);
p--;
}
s[++p] = dp1[i][j], w[p] = width + 1;
}
}
}
return ans;
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
printf("%d\n", solve());
}
return 0;
}