P1565 牛宫

这题真的神奇 $n^4$暴力开着O2嗖嗖飞起也是没谁了 ------------ 正解是$n^3$或者$n^3logn$ 因为我太菜了所以只会后者 其实这种做法就是把暴力的一层枚举转化为了二分 首先做一个竖着的前缀和（$sum[i][j]=sum[i-1][j]+a[i][j]$） 然后枚举$i$和$j$作为矩阵的上下两个边界 确定了上下边界，再用横着的前缀和算出每一列及其之前的总和 然后二分一个长度len，算一下矩形面积更新答案就好了 问题就在于如何check这个二分的答案 从len到m枚举，res取其中$t[i-len]$的最小值($t$为前缀和) 因为要求矩阵总和$>0$，所以当存在一个$i$满足$t[i]>res$时，这个答案就是可行的 如果这个最小值不是$t[i-len]$，那么还存在更优的解 n^3做法单调栈dp太神了orzzzzz ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; typedef long long ll; const int N=205; int n,m,ans; ll a[N][N],s[N][N],t[N]; inline ll read() { ll x=0; bool w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=0; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return w?x:-x; } inline bool check(int x) { ll res=0; for (reg int i=x;i<=m;i++) { res=min(res,t[i-x]); if (t[i]>res) return 1; } return 0; } inline int getlen() { int l=1,r=m,len=0; while (l<=r) { int mid=(l+r)>>1; if (check(mid)) len=mid,l=mid+1; else r=mid-1; } return len; } int main() { n=read(),m=read(); for (reg int i=1;i<=n;i++) for (reg int j=1;j<=m;j++) s[i][j]=s[i-1][j]+(a[i][j]=read()); for (reg int i=1;i<=n;i++) for (reg int j=i;j<=n;j++) { for (reg int k=1;k<=m;k++) t[k]=t[k-1]+s[j][k]-s[i-1][k]; ans=max(ans,(j-i+1)*getlen()); } printf("%d\n",ans); return 0; } ```