首先，我们来一波推论。
假设上图中 $ABCD$ 和 $EDEF$均满足题目条件，那么，
$f_A + f_D le f_C + f_B$
$f_C + f_F le f_D + f_E$
两柿子相加，自然得到： $f_A + f_F le f_B + f_E$
所以两个合法的矩阵可以合成一个大的合法矩阵
接着，考虑如何求出最大的矩阵：
先求出所有的合法矩阵，统计每一行中列合法的长度的分段前缀和。
接着，我们用单调栈，保存每个合法矩阵区间的纵坐标。为了保证可以拼凑出矩阵，所以遇到长度更短的，立即将前面的矩阵区间进行结算。 当然，最后不要忘了最右边的剩余未结算矩阵，放在循环外处理。
来个栗子：
对于波峰 $1,2$，遇到更短的$3$，令它们单成一个合法矩阵区间，用矩阵的面积公式结算。最后，我们会留下一个最短的矩阵区间，单独计算。
#include <bits/stdc++.h> using namespace std; #define N 1010 inline int read(){ int x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); } return x * s; } int stac[N], top = 0; // 存坐标 int ans = -666; int a[N][N], b[N][N]; int main(){ int n = read(), m = read(); for(int i = 1; i <= n; i++) for(int j = 1;j <= m; j++) a[i][j] = read(), b[i][j] = 1; for(int i = 1;i <= n; i++) for(int j = 1;j <= m; j++) if(a[i][j] + a[i-1][j-1] <= a[i-1][j] + a[i][j-1]) b[i][j] = b[i-1][j] + 1; for(int i = 1;i <= n; i++) for(int j = 1; j <= m; j++) if(b[i][j] == 1) b[i][j] = 0; stac[0] = 1; for(int i = 2;i <= n; in++){ top = 0; for(int j = 2;j <= m; j++){ while(top && b[i][j] <= b[i][stac[top]]){ int temp = b[i][stac[top]] * (j - stac[--top]); ans = max(ans, temp); } stac[++top] = j; } while(top){ ans = max(ans, b[i][stac[top]] * (m - stac[--top] + 1)); } } printf("%dn", ans); return 0; }
原文链接: https://www.cnblogs.com/wondering-world/p/13357823.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/369335
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
