[caioj]単調キュー3単調キュー
7119 ワード
【題意】1つのN*Mを与える数行列現在、1つのサブ行列を求めるには、サブ行列の最大値と最小値の差<=Cを求める.また、サブ行列の幅(横)は100(長(縦)を超えない.サブ行列の最大面積を求める.【入力フォーマット】1行目の2つの整数M(左右方向)、N(上下方向)、C(N,M<=500<=C<=10)次に、N行毎のM個数毎の数(-30000~30000)【出力フォーマット】サブマトリクスの最大面積【サンプル入力】10 15 4 41 40 41 38 39 40 40 40 40 40 40 40 40 40 40 39 40 43 36 37 35 42 44 41 39 40 38 40 41 38 38 38 38 33 36 37 32 36 38 40 39 39 39 39 39 39 40 40 41 43 41 39 39 39 39 39 39 39 39 42 36 39 39 39 39 39 39 39 39 39 39 39 39 39 39 40 41 31 36 41 41 40 40 40 40 40 40 40 40 40 40 42 39 39 39 39 42 40 40 39 39 39 39 399 39 39 40 41 40 39 40 47 45 43 41 41 40 39 42 42 41 39 40 39 42 42 42 42 41 44 43 46 41 42 42 45 42 42 42 42 42 44 41【サンプル出力】35
問題:
私の方法の複雑さは正しいようですが、ポイントが1つ詰まっていますか?私は料理が下手です......私の方法はまずmx[i][j][k]とmn[i][j][k]を前処理して、それぞれi行目j列の数からk数の中の最大の最小値を表して、それから列の起点jとスパンkを列挙して、それから1つの単調なキューで最大何行まで延長することができて、時間の複雑度はO(100しかし、私はまだカードに引っかかっています.
コード:
問題:
私の方法の複雑さは正しいようですが、ポイントが1つ詰まっていますか?私は料理が下手です......私の方法はまずmx[i][j][k]とmn[i][j][k]を前処理して、それぞれi行目j列の数からk数の中の最大の最小値を表して、それから列の起点jとスパンkを列挙して、それから1つの単調なキューで最大何行まで延長することができて、時間の複雑度はO(100しかし、私はまだカードに引っかかっています.
コード:
#include
#include
#include
#include
using namespace std;
const int maxn=505;
int m,n,c,a[maxn][maxn],start[maxn];
int mx[maxn][maxn][105];
int mn[maxn][maxn][105];
bool mark[maxn];
struct Queue{int mx,mn;}q[maxn];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
// freopen("airport9.in","r",stdin);
m=read();n=read();c=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=read(),mx[i][j][1]=mn[i][j][1]=a[i][j];
for(int k=2;k<=min(m,35);k++)
for(int i=1;i<=n;i++)
for(int j=1;j+k-1<=m;j++)
mx[i][j][k]=max(mx[i][j][k-1],a[i][j+k-1]),
mn[i][j][k]=min(mn[i][j][k-1],a[i][j+k-1]);
int ans=1;
q[0].mx=-999999999;
q[0].mn=999999999;
for(int i=1;i<=m;i++)start[i]=1;
for(int k=1;k<=min(m,35);k++)
{
for(int j=1;j+k-1<=m;j++)
{
if(mark[j])continue;
int head=1,tail=1,i;
for(i=start[j];i<=n;i++)
if(mx[i][j][k]-mn[i][j][k]<=c)break;
if(i==n+1){mark[j]=true;continue;}
start[j]=i;
if(mx[i][j][k]-mn[i][j][k]<=c)
{
q[1].mx=mx[i][j][k];q[1].mn=mn[i][j][k];
ans=max(ans,k);
for(int l=i+1;l<=n;l++)
{
if(mx[l][j][k]-mn[l][j][k]>c)
{
if((n-l)*k<=ans)break;
head=1;tail=0;continue;
}
while(head<=tail&&max(mx[l][j][k],q[head].mx)-min(mn[l][j][k],q[head].mn)>c)
{
head++;
q[head].mx=max(q[head].mx,q[head-1].mx);
q[head].mn=min(q[head].mn,q[head-1].mn);
}
if(head<=tail)ans=max(ans,k*(tail-head+2));
tail++;
q[tail].mx=mx[l][j][k];
q[tail].mn=mn[l][j][k];
q[head].mx=max(q[head].mx,q[tail].mx);
q[head].mn=min(q[head].mn,q[tail].mn);
}
}
}
}
printf("%d
",ans);
}