A Rectangular Barn

Mircea Pasoi -- 2003
Ever the capitalist, Farmer John wants to extend his milking business by purchasing more cows. He needs space to build a new barn for the cows.
FJ purchased a rectangular field with R (1 ≤ R ≤ 3,000) rows numbered 1..R and C (1 ≤ C ≤ 3,000) columns numbered 1..C. Unfortunately, he realized too late that some 1x1 areas in the field are damaged, so he cannot build the barn on the entire RxC field.
FJ has counted P (0 ≤ P ≤ 30,000) damaged 1x1 pieces and has asked for your help to find the biggest rectangular barn (i.e., the largest area) that he can build on his land without building on the damaged pieces.

PROGRAM NAME: rectbarn

INPUT FORMAT

Line 1: Three space-separated integers: R, C, and P.

Lines 2..P+1: Each line contains two space-separated integers, r and c, that give the row and column numbers of a damaged area of the field

SAMPLE INPUT (file rectbarn.in)

3 4 2
1 3
2 1

OUTPUT FORMAT

Line 1: The largest possible area of the new barn

SAMPLE OUTPUT (file rectbarn.out)

6

OUTPUT DETAILS

  1 2 3 4
 +-+-+-+-+
1| | |X| |
 +-+-+-+-+
2|X|#|#|#|
 +-+-+-+-+
3| |#|#|#|
 +-+-+-+-+

Pieces marked with 'X' are damaged and pieces marked with '#' are part of the new barn. 
题意:あなたに1つのn*mの行列をあげて、いくつかの格子は要らないで、最大のサブ行列の面积を求めます
解析:最大サブマトリクス問題は,点単位,次いで離散化再走査,複雑度O(P^2),格子単位走査,DPの2つの解法がある.複雑度はO(RC)で、データ量によって分析して、この問題は第2の方法を使うのに適しています.の具体的には王知昆の論文を見る
PS:この問題のデータは取れないですね.大きすぎるようですね.
コード:

/*
ID: 15114582
PROG: rectbarn
LANG: C++
*/
#include<cstdio>
#include<iostream>
using namespace std;
const int mm=3003;
int L[mm],H[mm],R[mm];
bool g[mm][mm];
int i,j,k,lm,rm,n,m,ans;
int main()
{
    freopen("rectbarn.in","r",stdin);
    freopen("rectbarn.out","w",stdout);
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(i=0;i<=n;++i)
            for(j=0;j<=m;++j)
                g[i][j]=1;
        while(k--)
        {
            scanf("%d%d",&i,&j);
            g[i][j]=0;
        }
        for(ans=j=0;j<=m;++j)H[j]=0,L[j]=1,R[j]=m;
        for(i=1;i<=n;++i)
        {
            for(lm=j=1;j<=m;++j)
                if(g[i][j])++H[j],L[j]=max(L[j],lm);
                else H[j]=0,L[j]=1,R[j]=m,lm=j+1;
            for(rm=j=m;j>=1;--j)
                if(g[i][j])
                {
                    R[j]=min(R[j],rm);
                    ans=max(ans,(R[j]-L[j]+1)*H[j]);
                }
                else rm=j-1;
        }
        printf("%d
",ans);
    }
	return 0;
}