首页 > 代码库 > 3736 【HR】万花丛中2
3736 【HR】万花丛中2
3736 【HR】万花丛中2
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
HR神犇在成功攻略ZX后，花心的他举办了一届选（yu）美（yue）大赛。
由于HR神犇有重度不规则形体恐惧症，所以他要求选美的女孩纸要站成一个正方形。因为HR神犇的眼光是非常之高的，所以他要求选出来的女孩美貌值总和最大，由于HR神犇的精力非常多，所以选出来的女孩数量没有限制。当然，一些女孩纸比较丑，美貌值可能为负数。而且，HR神犇的重度不规则形体恐惧症使他要求选出来的女孩纸形成一个矩形（不是正方形）（实心的）。
HR神犇决定，只要你成功帮他找出这个矩形，他就给你10000000000 mod 10元。
输入描述 Input Description
第一行一个整数n，表示正方形的边长。
接下来n行，每行n个整数，表示每个女孩的美貌值。
输出描述 Output Description
输出只有一个整数，表示最大的美貌值总和。
样例输入 Sample Input
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
样例输出 Sample Output
15
数据范围及提示 Data Size & Hint
对于30%的数据，1<=n<=10，美貌值<=100
对于50%的数据，1<=n<=50，美貌值<=104
对于100%的数据，1<=n<=200，美貌值不会超过int64的存储范围
分类标签 Tags 点此展开
暂无标签
AC代码：
#include<cstdio>#include<algorithm>#define ll long long#ifdef unix#define LL "%lld"#else#define LL "%I64d"#endifusing namespace std;const int N=1e3+10;int n;ll ans,s[N][N],a[N][N];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf(LL,&a[i][j]); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=i;k<=n;k++){ for(int l=j;l<=n;l++){ ans=max(ans,s[k][l]-s[i-1][l]-s[k][j-1]+s[i-1][j-1]); } } } } printf(LL,ans); return 0;}
3736 【HR】万花丛中2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。