题目链接:
POJ:http://poj.org/problem?id=1050
HDU:http://acm.hdu.edu.cn/showproblem.php?pid=1081
题意:给出一个n*n的矩阵,正负均有。求一个子矩阵使得该子矩阵的和尽可能的大。
思路:类似于最大子段和,即将前i行至前j行的矩阵压缩成一行,利用一个数组c,c[k]表示第k列从第i行到第j行的和,接下来只需对数组c求最大子段和,结果即为第i行到第j行中的最大子矩阵和。
代码:
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 5e2 + 10;
const int INF = 0x3f3f3f3f;
long long a[N][N];
long long c[N];
int n, m;
long long getAns() {
long long ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
long long res = 0;
for (int k = 1; k <= m; k++) {
c[k] = (i == j ? a[i][k] : c[k] + a[j][k]);
if (res < 0)
res = c[k];
else
res = res + c[k];
ans = max(res, ans);
}
}
}
return ans;
}
int main() {
while (scanf("%d%d", &m, &n) != EOF) {
long long _max = -INF;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%lld", &a[i][j]);
_max = max(_max, a[i][j]);
}
}
// 若矩阵全为负数,则认为结果为0
long long ans = (_max < 0LL ? 0 : getAns());
printf("%lld\n", ans);
}
return 0;
}
文章浏览阅读43次。本文我们只谈界面。 大部分人最开始学习编程是Console,搞个计算器啥的,后来高级一点能做一个俄罗斯方块出来。很羡慕那些能做出界面的,于是大二学了MFC,一开始看《深入浅出》怎么都搞不懂,后来我们班的一个女生教了我两个小时,我一下子通畅了,用GDI半个月苦哈哈的做了第一个当时觉得还能看得界面(不用任何控件哦)连箭头都是用三根线拼起来的! ...
文章浏览阅读715次,点赞11次,收藏12次。这里可以看到,在打印时传入的地址与1中的head地址并不相同,从而在读取链表head地址时并不是1中的head的地址,也就出现了如上的情况。这里楼主也不清楚具体是什么导致了传入地址的变化,还望有大佬指点。我也参考了另一位楼主的解决办法,如下。既然通过逐行运行得知是传入PrintList的地址不一致而导致的,那么这里将CreateList函数的类型进行修改,并返回head的地址。当数据元素输入完后,红圈这里head指向的地址我们先记住,接下来我们对输入的数据进行打印。第一次写文章,如有问题还望有大佬指点。_c语言链表创建时出现访问权限冲突怎么办
文章浏览阅读3.2k次。跑批问题:Caused by: java.io.IOException: Added a key not lexically larger than previous. Current cell = 10000000414/aml_custinfo:address/1594509705240/Put/vlen=42/seqid=0, lastCell = 10000000414/aml_custinfo:watchcustflag/1594509705240/Put/vlen=1/seqid=0报错_added a key not lexically larger than previous
文章浏览阅读378次。Hi,大家好;今天是双12,大家剁手了没。今天给大家带来的是《Linux查看服务器上的硬件信息》本篇文章的示例全部是在服务器(Inspur SA5112M4)上实现的,有些命令在虚拟机上达不到效果查看服务器型号、序列号root@zhangdaifu# dmidecode -s system-serial-numberroot@zhangdaifu# dmidecode -t system | gr..._crystal beach /dma
文章浏览阅读2.9k次,点赞3次,收藏6次。MATLAB一元函数与二元函数求极小值_matlab中求解2变量函数的极小值
文章浏览阅读734次。Mysql的三大范式,存储引擎、索引、sql的执行计划、count()计数的区别,事务,简单sql调优,索引失效场景、jdbcTemplate查询类获取时间没有时分秒、连接mysql时区配置,jaskson转json时区配置..._mysql possible key有值但是key为null
文章浏览阅读1.2k次,点赞25次,收藏29次。数据结构快速排序详解.内容包括:快排的简介及思想,快排代码实现的三种方式,快排的时间复杂度分析,快排的优化,快排的非递归实现,快排的三路划分算法.
文章浏览阅读461次。1.在PublicController控制器中写好判断手机端方法。<?phpnamespace Home\Controller;use Think\Controller;class PublicController extends Controller { //判断是否是手机端还是电脑端 function isMobile(){ // 如果有Ht_php判断手否电脑端</div>
文章浏览阅读4.9k次。本文实例讲述了python中列表元素连接方法join用法。分享给大家供大家参考。具体分析如下:创建列表:>>> music = ["Abba","Rolling Stones","Black Sabbath","Metallica"]>>> print music输出:['Abba', 'Rolling Stones', 'Black Sabbath', 'Me..._python将list使用/n连接起来
文章浏览阅读561次。文章目录一、表格的作用二、表格骨架标签三、表格的样式四、表格其他标签五、合并单元格六、综合练习一、表格的作用在CSS还未普及的时候一些简单的网站使用表格布局是十分快捷的,开发人员只要按照需求,简单的对表格进行行列的拆分,就能实现设计页面的布局;随着互联网的发展以及CSS的普及用户的审美提升,表格布局渐渐淡出了布局手段行列。虽然表格现在不常用于布局,但是在展示一些后台数据的时候表格可以让数据显示的非常清晰规整,阅读起来十分方便,所以我们常用表格来展示一些数据。二、表格骨架标签<table>_html表格例子
文章浏览阅读284次。## 点击蓝色字体可跳转至相应文章,尔后文章待续... 1.New Code day11. 打印100~200 之间的素数 2. 输出乘法口诀表 3. 判断1000年---2000年之间的闰年 2.New Code day21.给定两个整形变量的值,将两个值的内容进行交换。 2.不允许创建临时变量,交换两个数的内容(附加题) 3.求10 个整数中最大值。 ..._方向作业
文章浏览阅读1.1k次,点赞11次,收藏8次。scheduler通过 kubernetes 的监测(Watch)机制来发现集群中新创建且尚未被调度到 Node 上的 Pod。 scheduler会将发现的每一个未调度的 Pod 调度到一个合适的 Node 上来运行。 scheduler会依据下文的调度原则来做出调度选择。Controller Manager作为集群内部的管理控制中心,负责集群内的Node、Pod副本、服务端点(Endpoint)、命名空间(Namespace)、服务账号(ServiceAccount)、资源定额(ResourceQuot_kube-controller-manager 配置