BZOJ-5085: 最大

Description

给你一个n×m的矩形，要你找一个子矩形，价值为左上角左下角右上角右下角这四个数的最小值，要你最大化矩形的价值。n,m<=1000

二分+鸽巢原理
二分答案。如果存在两列，使得对应相同的两行的位置合法，那么当前答案合法，对应的两行只有m^2个，暴力枚举所有在同一列的合法行对，进行标记，一旦被标记过了就返回true，反之返回false。时间复杂度o(logw*m*m)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define R register 
const int inf=0x3f3f3f3f;
int n,m,mp[1100][1100];
int v[1100][1100];
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2) ? EOF:*p1++;
}
inline void read(int &x)
{
    char ch=nc(); int f=1;
    while(!isdigit(ch)) {if(ch=='-') f=0; ch=nc();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=nc();
    x= f ? x:-x;
}
bool check(int x)
{
    static int tim,z[1100];
    ++tim; R int i,j,k,top=0;
    for(i=1;i<=n;top=0,++i)
        for(j=1;j<=m;++j) if(mp[i][j]>=x)
        {
            for(k=top;k;--k)
            {
                if(v[z[k]][j]==tim) return true;
                else v[z[k]][j]=tim;
            }
            z[++top]=j;
        }
    return false;
}
int main()
{
    int l=inf,r=-inf;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            read(mp[i][j]);
            if(mp[i][j]>r) r=mp[i][j];
            if(mp[i][j]<l) l=mp[i][j];
        }
    r++; int mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else r=mid;
    }
    printf("%d",l-1);
    return 0;
}