蓝桥 最大子矩阵 (dp)

简介: 蓝桥 最大子矩阵 (dp)
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

ll a[505][505];
int n, m;
int main(){
   
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++){
   
        for (int j=1; j<=m; j++){
   
            scanf("%lld", &a[i][j]);
        }
    }
    ll maxx=-9999;
    for (int i=1; i<=n; i++){
   
        ll t[505];
        memset(t, 0, sizeof(t));
        for (int j=i; j<=n; j++){
   
            for (int k=1; k<=m; k++){
   
                t[k]+=a[j][k];
            }
            ll tmax=-9999;
            for (int k=1; k<=m; k++){
   
                if (tmax<0)    tmax=0;
                tmax+=t[k];
                maxx=max(maxx, tmax);
            }
        }
    }
    printf("%lld", maxx);
    return 0;
}
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

ll a[255][255];
ll n, m, k;
int main(){
   
    scanf("%lld%lld%lld", &n, &m, &k);
    for (ll i=1; i<=n; i++){
   
        for (ll j=1; j<=m; j++){
   
            scanf("%lld", &a[i][j]);
        }
    }
    ll res=-1;
    for (ll i=1; i<=n; i++){
   
        ll t[505];
        memset(t, 0, sizeof(t));
        for (ll j=i; j<=n; j++){
   
            for (ll v=1; v<=m; v++){
   
                t[v]+=a[j][v];
            }
            ll sum=0;
            int pos=1;
            for (ll v=1; v<=m; v++){
   
                sum+=t[v];
                while (sum>k && pos<v){
   
                    sum-=t[pos];
                    pos++;
                }
                res=max(res, (j-i+1)*(v-pos+1));
            }
        }
    }
    printf("%d", res);
    return 0;
}
相关文章
|
6月前
树形dp常见类型——换根dp
树形dp常见类型——换根dp
|
测试技术
蓝桥 摆动序列 (dp)
蓝桥 摆动序列 (dp)
|
人工智能
动态规划(DP)——线性DP
动态规划(DP)——线性DP
|
机器学习/深度学习 人工智能
51nod 1055 最长等差数列 (dp好题)
51nod 1055 最长等差数列 (dp好题)
50 0
(闫氏dp分析法)AcWing 2. 01背包问题
(闫氏dp分析法)AcWing 2. 01背包问题
65 0
|
人工智能
洛谷P1115-最大子段和(DP-最大子段和)
洛谷P1115-最大子段和(DP-最大子段和)
洛谷P1115-最大子段和(DP-最大子段和)
【刷穿 LeetCode】516. 最长回文子序列 : 区间 DP 求解最长回文子序列问题
【刷穿 LeetCode】516. 最长回文子序列 : 区间 DP 求解最长回文子序列问题
洛谷P3360 ——偷天换日(dfs读入+树形DP+01背包)
洛谷P3360 ——偷天换日(dfs读入+树形DP+01背包)
92 0