HDU2870 Largest Submatrix
사고: 모든 자모 가 세 가지 가 있 을 수 있 습 니 다. a, b, c, 순서대로 최대 행렬, hdu 1505, hdu 1506 의 증 가 를 구 합 니 다.
#include<bits/stdc++.h>
using namespace std;
char M[1010][1010],nw[1010][1010];
int s[1010][1010],l[1010],r[1010],res,n,m;
void solve(char cc,char a,char b,char c)
{
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(M[i][j]==a||M[i][j]==b||M[i][j]==c) nw[i][j]=cc;
else nw[i][j]=M[i][j];
}
}
memset(s,0,sizeof(s));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(nw[i][j]==cc) s[i][j]=s[i-1][j]+1;
else s[i][j]=0;
}
}
for(int i=1;i<=n;i++){
s[i][0]=s[i][m+1]=-1;
for(int j=1;j<=m;j++) l[j]=r[j]=j;
for(int j=1;j<=m;j++){
while(s[i][l[j]-1]>=s[i][j]) l[j]=l[l[j]-1];
}
for(int j=m;j>=1;j--){
while(s[i][r[j]+1]>=s[i][j]) r[j]=r[r[j]+1];
}
for(int j=1;j<=m;j++) res=max(res,(r[j]-l[j]+1)*s[i][j]);
}
}
int main()
{
while(~scanf("%d %d",&n,&m)){
res=0;
//getchar();
for(int i=1;i<=n;i++){
scanf("%s",M[i]+1);
//getchar();
}
solve('a','w','y','z');
solve('b','w','x','z');
solve('c','x','y','z');
printf("%d
",res);
/*
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%c",M[i][j]);
}
printf("
");
}*/
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
