[FZYZ某NOIP模拟赛]【求一矩阵中面积最大的子矩阵,使得Sum{a[i][j]}>0】【两个单调栈】★★

【题目大意】
给定一个m*n的矩阵,每个格子有一个a[i][j],求一个子矩阵,使得这个子矩阵里面的a[i][j]之和>0,使之面积最大。
输入m , n
然后m行,n列。表示a[i][j]。
m,n<=200
【算法分析】
我们枚举子矩阵的上边界i和下边界j。然后令w[k]=Sum{a[t][k]} i<=t<=j。
然后压成一维的情况。
先求出前缀和,Sum[i]=w[1]+w[2]+…+w[i]。特别地SUm[0]=0
然后变成求一个Max( (i-j) ) 其中 i>j 且 Sum[i]-Sum[j]>0
一、
对于红色的东西而言,
假设i>j && Sum[i]>Sum[j],那么j就废了,不需要枚举作为右边界。(很显然吧T_T)
二、
对于蓝色的东西而言,
假设i

于是我们开两个栈,
、一个以i递增序处理,搞出一个对于右边界有用的集合。(栈A)
另一个以i递减序处理,搞出一个对于左边界有用的集合。(栈B)


然后最后这两个栈里会有这样的性质:
栈A:从栈底到栈尾,关于i递增,同时关于Sum[i]递减。
栈B:从栈底到栈尾,关于i递减,同时关于Sum[i]递增。


好了,这样我们就可以很简单地用两个指针i,j,一个指针指着栈A元素,一个指针指着栈B元素。
然后双指针维护最长区间使得 pos[i]>pos[j] 且 Sum[pos[i]]-Sum[pos[j]]>0。


好了,解决了。这个一维问题的平摊复杂度为O(n)
【时间复杂度】O(m^2*n)
【空间复杂度】O(mn)
【其它】
嗯,其实我本不想写该题解题报告,
但是看到原来的解题报告的复杂度是O(m^2 * Sort(n) )
{其中Sort(n),表示将n个64位整形排序的复杂度,其中n<=200}
我觉得这种规模,还是快排最好了,那么就是O(m^2 n lg n)。
然后为了更多人了解这种比原解题报告更优的方法,我就写了该篇解题报告T_T。
【解释】
程序中把栈A的元素用v数组标记为可行,然后继续用了Q这个数组T_T,希望大家看起来不会纠结。
【CODE】
#include #include #include #include #include using namespace std;
const int N=205;
typedef long long lld;
int m,n;
int a[N][N];
lld w[N],Sum[N];
int Q[N];
int v[N];

void init(){
scanf("%d%d",&m,&n);
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
}

void solve(){
int i,j,k,ans=0,t,p;
for (i=1;i<=m;i++)
for (j=i;j<=m;j++){
for (k=1;k<=n;k++)
if (i==j) w[k]=a[i][k];
else w[k]+=a[j][k];
Sum[0]=0;
for (k=1;k<=n;k++){
Sum[k]=Sum[k-1]+w[k];
v[k]=0;
}
t=0;
for (k=1;k<=n;k++){
while (t>0 && Sum[Q[t]]<=Sum[k]) t--;
Q[++t]=k;
}
for (k=1;k<=t;k++) v[Q[k]]=1; t=0;
for (k=n;k>=0;k–){
while (t>0 && Sum[Q[t]]>=Sum[k]) t–;
Q[++t]=k;
}
p=t;
for (k=1;k<=n;k++)
if (v[k]){
while (p>0 && Sum[k]-Sum[Q[p]]<=0) p--;
if (p<=0 || Sum[k]-Sum[Q[p]]<=0) continue;
ans>?=(j-i+1)*(k-Q[p]);
}
}
printf("%dn",ans);
}

int main(){
init();
solve();
return 0;
}

加入对话

8条评论

  1. 回复IT_intheway:据给我题目的人说…这是有版权的…不能乱搞…而且好像本题为原创,所以没有链接,我只有数据。至于你说的影响,那样算出来的当前解是负数…怎么会有影响呢…

留下评论

回复 edward_mj 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注