已知一个长度为 n 的数组 a 和一个长度为 m 的数组 b, 问当两者相乘组成矩阵时求满足子矩阵中所有数相加小于 x 的最大面积
数学题, 这个问题可以转化为从 A 和 B 中找到一个子阵列, 使得这些子阵列的元素总和的乘积小于或等于 x, 并且它们的大小的乘积是最大的
- #include <bits/stdc++.h>
- #define ll long long
- using namespace std;
- const int maxn=2000+10;
- ll a[maxn],b[maxn],minsa[maxn],minsb[maxn];
- ll n,m,x;
- int main()
- {
- iOS::sync_with_stdio(false);cin.tie(0);
- cin>>n>>m;
- for(int i=0;i<n;i++){
- cin>>a[i];
- }
- for(int i=0;i<m;i++){
- cin>>b[i];
- }
- cin>>x;
- for(int i=0;i<maxn;i++)
- minsa[i]=minsb[i]=x+1;
- for(int i=0;i<n;i++)
- {
- ll sum=0;
- for(int j=i;j<n;j++)
- {
- sum+=a[j];
- minsa[j-i+1]=min(minsa[j-i+1],sum);
- }
- }
- for(int i=0;i<m;i++)
- {
- ll sum=0;
- for(int j=i;j<m;j++)
- {
- sum+=b[j];
- minsb[j-i+1]=min(minsb[j-i+1],sum);
- }
- }
- int ans=0;
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++){
- if(minsa[i]*minsb[j]<=x) ans=max(ans,i*j);
- }
- }
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2795797.html