最大子矩阵(openjudge noi-2.6基本算法之动态规划-1768)

这篇具有很好参考价值的文章主要介绍了最大子矩阵(openjudge noi-2.6基本算法之动态规划-1768)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

(1)题目

来源

OpenJudge - 1768:最大子矩阵

题目描述

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。

比如,如下4 * 4的矩阵

 0        -2        -7        0
 9         2        -6        2
-4         1        -4        1
-1         8         0       -2

它的最大子矩阵是

 9         2
-4         1
-1         8

 这个子矩阵的大小是15。

输入格式

输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。再后面的若干行中,依次(首先从左到右给出第一行的N个整数,再从左到右给出第二行的N个整数……)给出矩阵中的N²个整数,整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[-127, 127]

输出格式

输出最大子矩阵的大小。

输入样例

 4

 0        -2        -7        0
 9         2        -6        2
-4         1        -4        1
-1         8         0       -2

输出样例

15

(2)思路

1. 分析问题:分析已知和未知

这道题和最大子段和有所相同,但变成二维的了,推荐看这道题题解的小伙伴们先去看一下我的另一篇题解——最大子段和

最大子段和(洛谷--P1115)-CSDN博客

我们将进行以下几步:a. 枚举;b. 前缀和。

最大子矩阵(openjudge noi-2.6基本算法之动态规划-1768),算法,动态规划进入分析环节最大子矩阵(openjudge noi-2.6基本算法之动态规划-1768),算法,动态规划

a. 枚举

你以为我们会枚举四个顶点一个顶点和矩阵长宽左上顶点和右下顶点吗?

错!!!你想想那要写多少层循环!!!

如果真那么写,会是这样(从举的例子中可见,枚举左上顶点和右下顶点的时间复杂度应该少一点,那就枚举左上顶点和右下顶点得到所有子矩阵,求和再比较)

#include<iostream>
using namespace std;
int main()
{
	int n,a[105][105],maxi=-130;//矩阵中整数的范围都在[-127, 127],maxi=-130
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) cin>>a[i][j]; //熟人 
	} 
	for(int x1=1;x1<=n;x1++)
	{
		for(int y1=1;y1<=n;y1++)//枚举左上顶点 
		{
			for(int x2=x1;x2<=n;x2++)
			{
				for(int y2=y1;y2<=n;y2++)//枚举右下顶点 
				{
					int sum=0;
					for(int i=x1;i<=x2;i++)
					{
						for(int j=y1;j<=y2;j++) sum+=a[i][j];//求和 
					}
					maxi=max(sum,maxi);//比较,求最大值 
				}
			}
		}
	}
	cout<<maxi; 
	return 0;
}

 你说这超不超时。

看来,只枚举是不行了

b. 前缀和

根据最大子段和的思路,我们可以先求出第一行第一列到剩下每个位置的子矩阵的和,再通过拼图的思路求和

for(int i=1;i<=n;i++)

{

        for(int j=1;j<=n;j++)//枚举各个位置

        {

                for(int m=1;m<=i;m++)//枚举第一行第一列到此位置的子矩阵

                {

                        for(int n=1;n<=j;n++) f[i][j]+=a[x][y];//求前缀和

                }
        }
}//求前缀和

拼图的思路作图如下

最大子矩阵(openjudge noi-2.6基本算法之动态规划-1768),算法,动态规划

假如,若要求红框内矩阵的和,要用(1,1)到红框内矩阵的右下角的矩阵的和(蓝框),减去剩下的部分,可以先减去橙框绿框,再把橙框绿框重叠的部分加回来(因为它被减了2次),就可以得到红框内矩阵的和了

修改内容:

有没有觉得4重循环还是多了?

前缀和的内容还可以简化哦!

但简化后的内容也要运用拼图思路

如图所示

最大子矩阵(openjudge noi-2.6基本算法之动态规划-1768),算法,动态规划

 如果要求红框矩阵内的和,可以用(黄框+绿框-重叠部分+蓝圈=红框)的公式求和。

可以这样做的原因是,黄框绿框以及重叠部分已经求过了!!!再加上蓝圈(a[i])就可以了。

具体代码如下

for(int i=1;i<=n;i++)

{

        for(int j=1;j<=n;j++)

        {

                f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];//拼图思路
        }
}

2. 数据定义:已知和未知的取名和类型

n:输入是一个N * N的矩阵

a[105][105]:输入的矩阵,0 < n <= 100

f[105][105]:第一行第一列到剩下每个位置的子矩阵的和,0 < n <= 100

sum:所有子矩阵的和

maxi:所有子矩阵中最大和,矩阵中整数的范围都在[-127, 127]

3. 数据输入:输入已知 

cin>>n;

for(int i=1;i<=n;i++)

{

        for(int j=1;j<=n;j++) cin>>a[i][j];

}

4. 数据计算:数字建模+设计算法

找前缀和的代码在前面已经给大家讲过了,下面是拼图的思路

for(int r1=1;r1<=n;r1++)

{

        for(int c1=1;c1<=n;c1++)//枚举左上顶点

        {

                for(int r2=r1;r2<=n;r2++)

                {

                        for(int c2=c1;c2<=n;c2++)枚举右下顶点

                        {

                                sum=f[r2][c2]+f[r1-1][c1-1]-f[r1-1][c2]-f[r2][c1-1];//拼图求和

                                maxi=max(maxi,sum);//比较

                                sum=0;//清零

                        }

                }
        }
}文章来源地址https://www.toymoban.com/news/detail-858894.html

(3)完整AC代码

#include<iostream>
using namespace std;
int main()
{
	int f1[105][105]={0};
	int n,a[105][105],f[105][105]={0},sum=0,maxi=-0x3f3f3f3f;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) cin>>a[i][j];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
		}
	}
	for(int r1=1;r1<=n;r1++)
	{
		for(int c1=1;c1<=n;c1++)
		{
			for(int r2=r1;r2<=n;r2++)
			{
				for(int c2=c1;c2<=n;c2++)
				{
					sum=f[r2][c2]+f[r1-1][c1-1]-f[r1-1][c2]-f[r2][c1-1];
					maxi=max(maxi,sum);
					sum=0;
				}
			}
		}
	}
	cout<<maxi;
	return 0;
}

到了这里,关于最大子矩阵(openjudge noi-2.6基本算法之动态规划-1768)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】Kadane‘s算法(动态规划、最大子数组和)

    Kadane\\\'s 算法是一种用于解决最大子数组和问题的动态规划算法。这类问题的目标是在给定整数数组中找到一个连续的子数组,使其元素之和最大(数组含有负数)。 算法的核心思想是通过迭代数组的每个元素,维护两个变量来跟踪局部最优解和全局最优解。 以下是Kadane’s算

    2024年03月22日
    浏览(98)
  • 【算法思考记录】动态规划入门!力扣2606. 找到最大开销的子字符串【Python3、动态规划】

    原题链接 动态规划(Dynamic Programming,简称 DP)是一种通过将原问题分解为相互重叠的子问题并只解决一次的方法来解决问题的算法优化技术。动态规划通常用于优化递归问题,通过存储子问题的解来避免重复计算,从而显著提高算法的效率。 动态规划的基本思想是将原问题

    2024年02月03日
    浏览(42)
  • 【算法题】动态规划中级阶段之跳跃游戏、最大子数组和、解码方法

    动态规划(Dynamic Programming,简称 DP)是一种解决多阶段决策过程最优化问题的方法。它是一种将复杂问题分解成重叠子问题的策略,通过维护每个子问题的最优解来推导出问题的最优解。 动态规划的主要思想是利用已求解的子问题的最优解来推导出更大问题的最优解,从而

    2024年02月11日
    浏览(47)
  • 剑指offer(C++)-JZ47:礼物的最大价值(算法-动态规划)

    作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 在一个mtimes nm×n的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向

    2024年02月05日
    浏览(63)
  • 【算法】Maximize Grid Happiness 最大化网格幸福感 动态规划

    给你四个整数 m、n、introvertsCount 和 extrovertsCount 。有一个 m x n 网格,和两种类型的人:内向的人和外向的人。总共有 introvertsCount 个内向的人和 extrovertsCount 个外向的人。 请你决定网格中应当居住多少人,并为每个人分配一个网格单元。 注意,不必 让所有人都生活在网格中

    2024年02月11日
    浏览(38)
  • 最大子段和——用蛮力算法,分治策略,动态规划算法三种求法(C语言)

    目录 一、题目 二、算法求解 1、蛮力算法 伪代码  算法分析 程序 2、分治策略 伪代码 算法分析 程序 3、动态规划算法 伪代码 算法分析 程序 设A=a1,a2,...,an是n个整数的序列,称ai,....,aj为该序列的连续子序列,其中1=i=j=n,子序列的元素之和称为A的子段和: 例如,A=-2,11,-4,1

    2024年01月24日
    浏览(52)
  • 【动态规划】动态规划算法基本概念,原理应用和示例代码

             动态规划(Dynamic Programming,简称DP)是一种解决多阶段决策问题的数学优化方法。它将原问题分解成若干个子问题,通过解决子问题只需解决一次并将结果保存下来,从而避免了重复计算,提高了算法效率。         通俗来讲,动态规划算法是解决一类具有重叠

    2024年01月21日
    浏览(45)
  • 算法 矩阵最长递增路径-(递归回溯+动态规划)

    牛客网: BM61 求矩阵的最长递增路径 解题思路: 1. 遍历二维矩阵每个位置,max求出所有位置分别为终点时的最长路径 2. 求某个位置为终点的最长路径时,使用动态规划dp对已经计算出的位置进行记录 3. 处理某个位置的最长路径时,如果dp[i][j]位置已有值,则直接返回即可,否则

    2024年02月07日
    浏览(41)
  • 【动态规划】矩阵链乘法——算法设计与分析

    对于矩阵 U p × q U_{ptimes q} U p × q ​ 和 V q × r V_{qtimes r} V q × r ​ , Z p × r = U V Z_{ptimes r}=UV Z p × r ​ = U V ,共需计算 p q r pqr pq r 次标量乘法,时间复杂度为 Θ ( p q r ) Theta (pqr) Θ ( pq r ) 矩阵乘法满足结合律,即 ( U V ) W = U ( V W ) (UV)W=U(VW) ( U V ) W = U ( VW ) ,选择不同的结合

    2024年02月03日
    浏览(61)
  • 矩阵链乘法的动态规划算法_1

    上次我们学习了rod-cutting 问题的动态规划算法,初步了解求解动态规划过程的CRCC步骤,此步骤对于可以运用动态优化的问题非常有用,类似给大家提供了一套思维模板,让我们能更系统的思考和解决问题。本次我们将讨论矩阵链乘法的动态规划算法。 矩阵乘法 在讨论矩阵链

    2024年01月19日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包