[TIOJ 1470][ZJ b176] 區域 Area

作法：

其實這題蠻像最大子矩陣的。如果把每個兩個格子的交界處都看成一個點，並且幫他們編坐標，並且讓不合法的交界(沒有滿足題目的那個小於的需求)的值是0，合法的交界的值是1，就可以變回要求的就是這個東西的最大全部都是1的子矩陣。但還有些細節要注意，因為建出來的新的方格表大概會長這樣：

　０　１　１　０　１　１　１
１　０　０　１　１　１　１　１
　１　１　１　１　１　１　０
１　０　０　１　０　１　１　１

( 其中左上角坐標是(1,1) )
那麼我們要的其實是「四個角落的座標都是偶數」的子矩陣，並且剩下的格子不造成影響，所以可以當作是全部都填1，這樣就可以直接套用最大子矩陣的算法，只要不在不為所求的格點上更新答案就可以了。這樣複雜度一樣是O(n^3)。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=200+10 ;
 
int G[maxn][maxn] ;
 
bool check(int x,int y)
{
    assert((x+y)%2) ;
    if(x==1 || y==1) return 0 ;
    if(x%2) return G[(x-1)/2][y/2]<G[(x+1)/2][y/2] ;
    else return G[x/2][(y-1)/2]<G[x/2][(y+1)/2] ;
}
 
struct P{int x,h;};
 
int h[maxn] ;
P st[maxn] ;
 
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
        scanf("%d",&G[i][j]) ;
    int ans=0 ;
    for(int i=2;i<=2*n;i++)
    {
        for(int j=1;j<=2*m;j++)
            h[j]=  (((i+j)%2) && !check(i,j)) ? 0 : h[j]+1 ;
        if(i%2) continue ;
 
        int sz=0 ;
        for(int j=1;j<=2*m;j++)
        {
            while(sz>=2 && st[sz-2].h>=h[j]) sz-- ;
            if(sz && st[sz-1].h > h[j]) st[sz-1].h = h[j] ;
            if(j%2) continue ;
            st[sz++]=(P){j,h[j]} ;
            for(int k=0;k<sz;k++) ans=max(ans,
                ((j-st[k].x+2)/2)*((st[k].h+1)/2)) ;
        }
    }
    printf("%d\n",ans) ;
}