[TIOJ 1643] 建築工程規劃

我個人認為正解應該不會跟我的作法一樣，題目的 0 <= L <= 20 感覺就有有梗的作法，但我沒有想到，只想到理論上複雜度為 O( N^2 M log M ) 的作法。

作法：

考慮枚舉所求矩形的上下邊界，在確定上下邊界之後，就可以把問題壓回一維的問題，變成一個數列然後詢問最長的最大最小差 <= L 的問題，這可以用滑動窗口在O( n log n )解決，其中 n 是數列長度。另外假設我們現在的上下邊界是第 x 排和第 y 排，那麼轉為一維後會變成需要 max( i = x ~ y ) a[ i ][ j ] 的值( min 也是 )，其中 j = 1 ~ m ，當然每次重算一遍太慢了，考慮當 y 多 1 的時候這個值其實只有多考慮一個數，所以可以直接維護 min 和 max 們。

另外我加的剪枝是，如果當前能夠形成的最大矩形比目前的解還小，就不要再作下去了。還有如果遇到有單一一個點的 max 和 min 的差已經超過 L 了，就直接把當前區間跳到這個點的後面，以節省時間。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10 ;
 
int G[maxn][maxn] ;
int L,n,m,ans ;
int mi[maxn] , ma[maxn] ;
map<int,int> mp ;
 
int solve(int x,int y)
{
    for(int i=1;i<=m;i++)
    {
        mi[i]= x==y ? G[x][i] : min(mi[i],G[y][i]) ;
        ma[i]= x==y ? G[x][i] : max(ma[i],G[y][i]) ;
    }
    int ret=0 ;
    mp.clear();
    for(int i=1,j=0;i<=m;i++)
    {
        if((y-x+1)*(m-i+1)<ans) break ;
        if(j<m && ma[j+1]>mi[j+1]+L)
        {
            i=j+1 ; j++ ;
            mp.clear() ;
            continue ;
        }
        while(j<m)
        {
            j++ ;
            if( max(mp.empty() ? ma[j] : mp.rbegin()->first,ma[j]) -
               min(mp.empty() ? mi[j] : mp.begin()->first,mi[j]) > L )
                { j-- ; break ; }
            mp[mi[j]]++ ; mp[ma[j]]++ ;
        }
        ret=max(ret,j-i+1) ;
        if(j==i-1) j++ ;
        else
        {
            auto it=mp.find(mi[i]) ;
            if(!(--it->second)) mp.erase(it) ;
            it=mp.find(ma[i]) ;
            if(!(--it->second)) mp.erase(it) ;
        }
    }
    return ret ;
}
 
main()
{
    scanf("%d%d%d",&n,&m,&L) ;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
        scanf("%d",&G[i][j]) ;
    ans=0 ;
    for(int i=1;i<=n;i++) for(int j=i;j<=n;j++)
        ans=max(ans,(j-i+1)*solve(i,j)) ;
    printf("%d\n",ans) ;
}