首页 > itarticle > wannfly挑战赛19 b 矩阵

wannfly挑战赛19 b 矩阵

admin 11月 13, 2020 0

给一个$R·C$的矩阵，问满足以下三个条件的最大子矩阵。
子矩阵不超过 $X$ 行。
子矩阵不超过 $Y$ 列。
子矩阵中 $0$ 的个数不能超过 $Z$ 个。
$(R,C,X,Yle500，Zle R·C)$

题解

枚举符合条件的两行
用剩下两个条件单调队列列的范围
时间复杂度 $O(R·C^2)$

代码


using namespace std;
typedef long long ll;

ll n,m,c[505][505],X,Y,Z, a[505][505], lin[505][505], nowc[505], nowlin[505];
ll ans;

int ()
{
    scanf("%lld%lld%lld%lld%lld", &n,&m,&X,&Y,&Z);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++){
            scanf("%lld", &a[i][j]);
            c[i][j]=c[i-1][j]+a[i][j];
            lin[i][j]=lin[i-1][j]+(a[i][j]==0);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n&&(j-i+1)<=X;j++)
        {
            for(int k=1;k<=m;k++)
            {
                nowc[k]=c[j][k]-c[i-1][k]+nowc[k-1];
                nowlin[k]=lin[j][k]-lin[i-1][k]+nowlin[k-1];
            }
            deque<pair<ll,int>>q;
            q.push_back({0, 0});
            for(int l=1,r=1;r<=m;r++)
            {
                while(r-l+1>Y || nowlin[r]-nowlin[l-1]>Z) l++;
                while(!q.empty() && q.back().first>nowc[r]) q.pop_back();
                while(!q.empty() && q.front().second<l-1)q.pop_front();
                q.push_back({nowc[r], r});
                ans=max(ans, nowc[r]-q.front().first);
            }
        }
    }
    printf("%lldn", ans);
}