[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;
}