P1565 牛宫

2018-09-03 20:41:10


这题真的神奇

$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;
}