题目链接

https://vjudge.net/contest/398864#problem/C

解题思路

代码1：

dp[i][j]表示以(1,1)为左上角，以(i,j)为右下角的矩阵的和；
枚举矩阵的左边界和右边界，再利用尺取法选取上边界和下边界，判断选取的子矩阵的和是否小于等于k。
这个好理解。

代码2：

大致思路一样，枚举左边界和右边界，尺取上边界和下边界。
不同之处在代码中注释。

AC代码1：

#include<bits/stdc++.h>
#define ll long long
#define sc(x) scanf("%lld",&x)
#define pr(x) printf("%lld\n",x)
using namespace std;
const int N=300;
ll ans,n,m,K,dp[N][N];
int main(){
    sc(n);sc(m);sc(K);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            sc(dp[i][j]);
            dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+dp[i][j];
        }

    for(int wL=1;wL<=m;wL++)
        for(int wR=wL;wR<=m;wR++){
            ll p1=1,p2=1;
            while(p1<=n && p2<=n){
                if(dp[p2][wR]-dp[p2][wL-1]-dp[p1-1][wR]+dp[p1-1][wL-1]<=K) ans=max(ans,(wR-wL+1)*(p2-p1+1)),p2++;
                else p1++,p2=p1;
            }
        }

    if(ans==0) cout<<-1<<endl;
    else pr(ans);
}

AC代码2：

#include<bits/stdc++.h>
#define ll long long
#define sc(x) scanf("%lld",&x)
#define pr(x) printf("%lld\n",x)
using namespace std;
const int N=300;
ll n,m,K,ans;
ll dp[N],sum[N][N];//两个表示前缀和数组，sum[i][j]表示第i行，前j列的和，dp[i]表示前i行，从第L列到第R列的和//配合下面代码会好理解点
ll h[N],mp[N][N];//h[i]表示第i行，从第L列到第R列的和，mp单纯存的矩阵
int main(){
    sc(n);sc(m);sc(K);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            sc(mp[i][j]);
            sum[i][j]=sum[i][j-1]+mp[i][j];//每一行的前缀和存在sum数组中
        }
    }

    for(int i=1;i<=m;i++)//枚举左边界
        for(int j=i;j<=m;j++){//枚举右边界
            for(int k=1;k<=n;k++) h[k]=sum[k][j]-sum[k][i-1],dp[k]=dp[k-1]+h[k];//先算出从左边界到右边界范围内每一行对应的和，保存于h中；左边界到右边界范围内的前i行的子矩阵和保存于dp中
            ll p1=1,p2=1;
            while(p1<=n && p2<=n){//尺取，这个条件很关键，容易漏p2<=n
                if(dp[p2]-dp[p1-1]<=K) ans=max(ans,(j-i+1)*(p2-p1+1)),p2++;
                else p1++,p2=p1;
            }
        }

    if(ans==0) cout<<-1<<endl;
    else pr(ans);    
}

二维前缀和例题

最大子阵