蓝桥 最大子矩阵 (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月前
【每日一题Day242】LC1262可被三整除的最大和 | 贪心 dp
【每日一题Day242】LC1262可被三整除的最大和 | 贪心 dp
48 0
|
5月前
|
算法
【算法优选】 动态规划之两个数组dp——壹
【算法优选】 动态规划之两个数组dp——壹
|
6月前
【每日一题Day126】LC1140石子游戏Ⅱ | 博弈dp 记忆化搜索
【每日一题Day126】LC1140石子游戏Ⅱ | 博弈dp 记忆化搜索
47 0
|
测试技术
蓝桥 摆动序列 (dp)
蓝桥 摆动序列 (dp)
|
人工智能
动态规划(DP)——线性DP
动态规划(DP)——线性DP
|
人工智能 算法 测试技术
LeetCode 双周赛 101,DP / 中位数贪心 / 裴蜀定理 / Dijkstra / 最小环
这周比较忙,上周末的双周赛题解现在才更新,虽迟但到哈。上周末这场是 LeetCode 第 101 场双周赛,整体有点难度,第 3 题似乎比第 4 题还难一些。
97 0
|
机器学习/深度学习 人工智能
51nod 1055 最长等差数列 (dp好题)
51nod 1055 最长等差数列 (dp好题)
50 0
|
机器学习/深度学习
蓝桥杯国赛 对局匹配(DP)
蓝桥杯国赛 对局匹配(DP)
蓝桥杯国赛 对局匹配(DP)
|
人工智能
洛谷P1115-最大子段和(DP-最大子段和)
洛谷P1115-最大子段和(DP-最大子段和)
洛谷P1115-最大子段和(DP-最大子段和)
|
算法 数据安全/隐私保护 C++
蓝桥杯第十五讲--复杂dp【例题】(一)
蓝桥杯第十五讲--复杂dp【例题】
129 0
蓝桥杯第十五讲--复杂dp【例题】(一)