UVA10827球面上的最大和
最大
2023-09-11 14:14:00 时间
题意:
最大子矩阵的加强版,就是给你一个n*n的矩阵,每个格子里面都有数字,然后我们在里面选择一个矩阵,使得矩阵中所有数字的和最大,而且这个题目说这个n*n的矩阵的最右边和最左边是相邻的,最上边和最下边是相邻的,这样就构成了一个球体。
思路:
我们依然可以用最大子矩阵的方法去做这个题目,我的大体思路是这样(方法不唯一),为了处理球的这个问题,我是给这个矩阵右侧,下侧,右下侧都扩出来一个矩阵,一共四个矩阵,这个比较容易理解也很容易想到,然后我们可以利用前缀和来降低一维,然后枚举矩阵列的范围(把那些列捏在一起),捏完之后就变成了最大连续子序列了,然后在去求最大连续子序列,还有就是这个最大连续子序列不能O(n)求出来,原因是上下拼接后注意最多只能跑n个,随意还有枚举,一开始些了个75*150*150*75的,TLE了一次,然后发现有些地方多次枚举了,然后小优化了下,变成75*75*75*75的,顺利AC了,大体就是这个样子,具体细节可以看代码,这个题目说思路说的有点别扭,大家要是没看懂就看下先下面的代码吧。
#include<stdio.h>
#include<string.h>
#define N 160
int ss[N][N] ,num[N][N];
int main ()
{
int t ,i ,j ,k ,n ,Ans;
scanf("%d" ,&t);
while(t--)
{
scanf("%d" ,&n);
int maxx = -100000;
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
{
scanf("%d" ,&num[i][j]);
num[i+n][j] = num[i][j+n] = num[i+n][j+n] = num[i][j];
if(maxx < num[i][j]) maxx = num[i][j];
}
if(maxx <= 0)
{
printf("%d\n" ,maxx);
continue;
}
memset(ss ,0 ,sizeof(ss));
for(i = 1 ;i <= n * 2 ;i ++)
for(j = 1 ;j <= n * 2;j ++)
ss[i][j] = ss[i][j-1] + num[i][j];
Ans = 0;
for(i = 1 ;i <= n ;i ++)
for(j = i ;j <= i + n - 1 && j <= n+n;j ++)
{
for(int ii = 1 ;ii <= n ;ii ++)
{
int now = 0;
for(int jj = ii ;jj <= ii + n - 1 && jj <= n + n;jj ++)
{
now += ss[jj][j] - ss[jj][i - 1];
if(now < 0) now = 0;
if(Ans < now) Ans = now;
}
}
}
printf("%d\n" ,Ans);
}
return 0;
}
最大子矩阵的加强版,就是给你一个n*n的矩阵,每个格子里面都有数字,然后我们在里面选择一个矩阵,使得矩阵中所有数字的和最大,而且这个题目说这个n*n的矩阵的最右边和最左边是相邻的,最上边和最下边是相邻的,这样就构成了一个球体。
思路:
我们依然可以用最大子矩阵的方法去做这个题目,我的大体思路是这样(方法不唯一),为了处理球的这个问题,我是给这个矩阵右侧,下侧,右下侧都扩出来一个矩阵,一共四个矩阵,这个比较容易理解也很容易想到,然后我们可以利用前缀和来降低一维,然后枚举矩阵列的范围(把那些列捏在一起),捏完之后就变成了最大连续子序列了,然后在去求最大连续子序列,还有就是这个最大连续子序列不能O(n)求出来,原因是上下拼接后注意最多只能跑n个,随意还有枚举,一开始些了个75*150*150*75的,TLE了一次,然后发现有些地方多次枚举了,然后小优化了下,变成75*75*75*75的,顺利AC了,大体就是这个样子,具体细节可以看代码,这个题目说思路说的有点别扭,大家要是没看懂就看下先下面的代码吧。
#include<stdio.h>
#include<string.h>
#define N 160
int ss[N][N] ,num[N][N];
int main ()
{
int t ,i ,j ,k ,n ,Ans;
scanf("%d" ,&t);
while(t--)
{
scanf("%d" ,&n);
int maxx = -100000;
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
{
scanf("%d" ,&num[i][j]);
num[i+n][j] = num[i][j+n] = num[i+n][j+n] = num[i][j];
if(maxx < num[i][j]) maxx = num[i][j];
}
if(maxx <= 0)
{
printf("%d\n" ,maxx);
continue;
}
memset(ss ,0 ,sizeof(ss));
for(i = 1 ;i <= n * 2 ;i ++)
for(j = 1 ;j <= n * 2;j ++)
ss[i][j] = ss[i][j-1] + num[i][j];
Ans = 0;
for(i = 1 ;i <= n ;i ++)
for(j = i ;j <= i + n - 1 && j <= n+n;j ++)
{
for(int ii = 1 ;ii <= n ;ii ++)
{
int now = 0;
for(int jj = ii ;jj <= ii + n - 1 && jj <= n + n;jj ++)
{
now += ss[jj][j] - ss[jj][i - 1];
if(now < 0) now = 0;
if(Ans < now) Ans = now;
}
}
}
printf("%d\n" ,Ans);
}
return 0;
}
相关文章
- 对最大团的理解
- sql server2017与IIS10的一个会话最大利用CPU核心好像都是64核心
- 微信小程序 - 文本框显示限制最大长度
- 【BZOJ1834】网络扩容(最大流,费用流)
- 面对面的口头信息传递对人决策的影响力最大
- 力扣解法汇总1742. 盒子中小球的最大数量
- 中国是未来十年全球最大光伏装机市场
- 浅谈最大流最小割定理
- 【刷题笔记】之牛客面试必刷TOP101(二叉树的前.中.后.层序遍历+按之字形顺序打印二叉树+二叉树的最大深度+二叉树中和为某一值的路径(一)+二叉搜索树与双向链表+判断是不是二叉搜索树)
- 全球最大海上风力发电厂在英国正式启用
- 最大的社交网络支持点赞以外的情绪,你还习惯么?
- [LeetCode] Max Area of Island 岛的最大面积
- [LeetCode] Find Largest Value in Each Tree Row 找树每行最大的结点值
- [LeetCode] 84. Largest Rectangle in Histogram 直方图中最大的矩形
- 智能家居的最大问题:我们真的需要物联网吗?
- 【bzoj1822】[JSOI2010]Frozen Nova 冷冻波 计算几何+二分+网络流最大流