前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Codeforces Round #513 C. Maximum Subrectangle(思维)

Codeforces Round #513 C. Maximum Subrectangle(思维)

作者头像
Ch_Zaqdt
发布2019-01-11 10:56:05
3770
发布2019-01-11 10:56:05
举报
文章被收录于专栏:Zaqdt_ACM

题目链接:http://codeforces.com/contest/1060/problem/C

       题意是输入n和m两组数,再输入一个值x,由这两组数组成一个n*m的矩阵a[i][j]表示a[i]*b[j]的值,在这个矩阵中找子矩阵,使得该子矩阵中所有的元素之和小于等于x,问所有符合条件的子矩阵中,面积最大的是多少。

       思路就是维护一个前缀和,然后去更新长度为1,2,3...n的子数组的和的最小值,然后联系两个数组遍历矩阵求解,直接看呆码吧...


AC代码:

代码语言:javascript
复制
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define maxn 20005
using namespace std;
ll a[maxn],b[maxn],_a[maxn],_b[maxn];
int n,m,x;

int main()
{
	scanf("%d%d",&n,&m);
	a[0] = 0; b[0] = 0;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i] += a[i-1];
	for(int i=1;i<=m;i++)scanf("%lld",&b[i]),b[i] += b[i-1];
	scanf("%d",&x);
	for(int i=1;i<=n;i++){
		_a[i] = inf;
		for(int j=i;j<=n;j++){
			_a[i] = min(_a[i], a[j] - a[j - i]);
		}
	}
	for(int i=1;i<=m;i++){
		_b[i] = inf;
		for(int j=i;j<=m;j++){
			_b[i] = min(_b[i], b[j] - b[j - i]);
		}
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(_a[i] * _b[j] <= x){
				ans = max(ans, i * j);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年10月06日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档