大意: 给定矩阵, 求选出一个最大矩形, 满足矩形内每个元素互不相同.

 

考虑枚举上下左三个边界, 求出最大右边界的位置.

注意到固定上边界, 下边界递推时, 每个左边界对应最大右边界是单调不增的.

所以只需考虑下边界所在行的影响, 与之前的取最小即可.

用$set$求的话复杂度是$O(n^3logn)$, 没有卡过去.

$set$改成$vEB$树的话复杂度可以达到$O(n^3loglogn)$, 或许可以过.

实际上可以发现, 下边界所在行每个点的最大右边界在上边界递减时是非增的, 可以倒序枚举上边界, 这样就可以达到复杂度$O(n^3)$.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define REP(i,a,n) for(int i=a;i<=n;++i)#define PER(i,a,n) for(int i=n;i>=a;--i)using namespace std;const int N = 410;int n, m, a[N][N], R[N][N];int l1[N], r1[N], vis[N*N];int main() {	scanf("%d%d", &n, &m);	REP(i,1,n) REP(j,1,m) scanf("%d",a[i]+j);	memset(R,0x3f,sizeof R);	int ans = 0;	REP(D,1,n) {		REP(i,1,m) r1[i]=m+1,l1[i]=0;		//l1[i] 是行范围在[U,D]内, 列在i左侧, 存在与a[D][i]相等的最接近i的列数		//r1[i] 是行范围在[U,D]内, 列在i右侧, 存在与a[D][i]相等的最接近i的列数		//R[U][i] 为上边界U, 下边界D, 左边界i的矩形的最大右边界		PER(U,1,D) {			int now = 1;			REP(i,1,m) {				now = max(now, i);				while (now
         
          l1[i]&&!vis[a[U][now]]&&!vis[a[D][now]]) {					if (U!=D&&a[U][now]==a[D][now]) break;					vis[a[U][now]] = vis[a[D][now]] = 1;					--now;				}				vis[a[U][i]] = vis[a[D][i]] = 0;				l1[i] = max(l1[i], now);			}			REP(i,1,m) {				R[U][i] = min(R[U][i],r1[i]-1);				R[U][l1[i]] = min(R[U][l1[i]],i-1);			}			PER(i,1,m) {				R[U][i] = min(R[U][i], R[U][i+1]);				ans = max(ans, (D-U+1)*(R[U][i]-i+1));			}		}	}	printf("%d\n", ans);}
         
        
       
      
     

 

还有一种编码非常简单的区间$DP$做法.

设$f_{i,l,r}$为下边界$i$,左右边界$l,r$的最小上边界值, 有转移

$f_{i,l,r}=max\{f_{i-1,l,r},f_{i,l+1,r},f_{i,l,r-1},a_{i,l}$与$a_{1..i,r}$的限制$,a_{1..i,l}$与$a_{i,r}$的限制$\}$

#include 
     
      #include 
      
       #include 
       
        #define REP(i,a,n) for(int i=a;i<=n;++i)using namespace std;const int N = 402;int n,m,a[N][N],f[N][N],pre[N][N*N];int main() {	scanf("%d%d", &n, &m);	REP(i,1,n) REP(j,1,m) scanf("%d",a[i]+j);	int ans = 0;	REP(i,1,n) REP(d,1,m) {		for (int l=1,r=d; r<=m; ++l,++r) {			if (l==r) f[l][l]=max(f[l][l],pre[l][a[i][l]]);			else if (a[i][l]==a[i][r]) f[l][r] = i;			else {				f[l][r]=max({f[l][r],f[l][r-1],f[l+1][r],pre[r][a[i][l]],pre[l][a[i][r]]});			}			ans = max(ans, (i-f[l][r])*(r-l+1));		}		REP(j,1,m) pre[j][a[i][j]]=i;	}	printf("%d\n", ans);}