1 Star 0 Fork 0

util6/算法刷题c++

加入 Gitee
与超过 1400万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
AcWing4395MaximumSubmatrix.cpp 1.12 KB
一键复制 编辑 原始数据 按行查看 历史
util6 提交于 2022-04-03 21:33 +08:00 . 默认的
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
/**
* https://www.acwing.com/problem/content/description/4398/
* 思路:
* 首先,不用把矩阵构造出来,子矩阵的面积和就是2个数组区间和的乘积
* 预处理出每个区间长度下,区间和的最小值
* 枚举区间每个长度,算出结果
*/
const int N = 2005;
int n,m;
int s1[N],s2[N];
int a[N],b[N];
int main(){
cin>>n>>m;
for(int i = 1; i <=n; i++) {
int x;
cin>>x;
s1[i] = s1[i-1]+x;
}
for(int i = 1; i <=m; i++) {
int x;
cin>>x;
s2[i] = s2[i-1]+x;
}
int limit;
cin>>limit;
//枚举每个区间长度
memset(a,0x3f,sizeof a);
memset(b,0x3f,sizeof b);
for(int i = 1; i <=n; i++) {
for(int j = 1; j+i-1 <=n; j++) {
a[i] = min(s1[j+i-1]-s1[j-1],a[i]);
}
}
for(int i = 1; i <=m; i++) {
for(int j = 1; j+i-1 <=m; j++) {
b[i] = min(s2[j+i-1]-s2[j-1],b[i]);
}
}
int ans = 0;
for(int i = n; i; i--) {
for(int j = m; j ; j--) {
//注意这里相乘会报int
if ((LL)a[i]*b[j]<=limit){
ans = max(ans,i*j);
}
}
}
cout<<ans;
}
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/liuyutaocode/cppCode.git
git@gitee.com:liuyutaocode/cppCode.git
liuyutaocode
cppCode
算法刷题c++
master

搜索帮助