二维数组之后续篇章(张硕---李帅)

2023-10-25 04:30

本文主要是介绍二维数组之后续篇章(张硕---李帅),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

又是一个令人头疼的题目啊。。。。

这次又增加难度了!!!找二维数组中的最大子数组,要求联通即可:

开始自己想法是枚举,然后找规律,后来发现这种方法实在是弱爆了,而且不好实现,后来通过查阅资料,发现大牛们都推荐动态规划,下面把思想陈述一下:

首先,将二维问题降维处理:

例如,用2 维数组a[1 : m][1 : n]表示给定的m行n列的整数矩阵。子数组a[i1 : i2][j1 : j2]表示左上角和右下角行列坐标分别为(i1, j1)和(i2, j2)的子矩阵。

先按照行排列出所有可能区间,然后,再去求列的范围。

更详细的,当行区间确定之后,剩下就是确定列区间了,一旦确定列区间,最大子矩阵就确定了。

当行区间确定之后,求列区间的方法,可以转化成一维数组的最大连续子序列的问题:对行区间[i1, j1],依次对列进行求和,就得到n个数据的以为数组,根据最大连续子序列的和的求法,就可以获得连续子序列最大和。

仍然用nGreatestNum来记录最大值,算出一个子矩阵的和,就进行比较即可。

算法在设计中。。。

转载于:https://www.cnblogs.com/zsjy/p/3634613.html

这篇关于二维数组之后续篇章(张硕---李帅)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/280017

相关文章

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

HDU 2159 二维完全背包

FATE 最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能

C语言:柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t;t = malloc(sizeof(Test) + 11);strcpy(t->arr,

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组,顾名思义,就是一组数。 假如班上有 30 个同学,让你编程统计每个人的分数,求最高分、最低分、平均分等。如果不知道数组,你只能这样写代码: int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou

计算数组的斜率,偏移,R2

模拟Excel中的R2的计算。         public bool fnCheckRear_R2(List<double[]> lRear, int iMinRear, int iMaxRear, ref double dR2)         {             bool bResult = true;             int n = 0;             dou

C# double[] 和Matlab数组MWArray[]转换

C# double[] 转换成MWArray[], 直接赋值就行             MWNumericArray[] ma = new MWNumericArray[4];             double[] dT = new double[] { 0 };             double[] dT1 = new double[] { 0,2 };

BT天堂网站挂马事件后续:“大灰狼”远控木马分析及幕后真凶调查

9月初安全团队披露bt天堂网站挂马事件,该网站被利用IE神洞CVE-2014-6332挂马,如果用户没有打补丁或开启安全软件防护,电脑会自动下载执行大灰狼远控木马程序。 鉴于bt天堂电影下载网站访问量巨大,此次挂马事件受害者甚众,安全团队专门针对该木马进行严密监控,并对其幕后真凶进行了深入调查。 一、“大灰狼”的伪装 以下是10月30日一天内大灰狼远控的木马样本截图,可以看到该木马变种数量不