http://poj.org/problem?id=1050 (题目链接)

题意

  求二维最大子矩阵

Solution

  数据好像很水,N最大才100,N^4大暴力都可以随便水过。

  其实有N^3的做法。枚举矩阵上下边界,然后把中间的一大坨看作是一维的一条直线,O(n)的做最长子段和即可。当然记得要预处理出前缀和。

代码

// poj1050
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi 3.1415926535898
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; int n,a[1010][1010],sum[1010][1010]; int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) scanf("%d",&a[i][j]),sum[i][j]=a[i][j]+sum[i][j-1];
int ans=-inf;
for (int i=1;i<=n;i++)
for (int j=i;j<=n;j++) {
int s=0;
for (int k=1;k<=n;k++) {
s+=sum[k][j]-sum[k][i-1];
if (s<0) s=0;
else ans=max(ans,s);
}
}
printf("%d",ans);
return 0;
}

  

最新文章

  1. Apache Rewrite匹配问号的问题
  2. .html()和.text()的区别
  3. Apache2.4.6 添加虚拟主机
  4. HLS视频点播&amp;直播初探
  5. CentOS 下用的是lnmp 的包配置Nginx 下的CI伪静态(搞爽了)
  6. Quoted-printable 编码介绍、编码解码转换
  7. 未能加载文件或程序集&ldquo;XXX&rdquo;或它的某一个依赖项。试图加载格式不正确的程序。
  8. angular2 的依赖注入
  9. DB天气 Alpha版使用说明
  10. 转:C语言宏定义时#(井号)和##(双井号)的用法
  11. 冒泡排序java
  12. emacs quick open and jump file (or buffer) which name is current word
  13. 你需要了解的高可用方案之使用keepalived搭建双机热备一览
  14. 9、Libgdx的输入处理
  15. docker简单介绍----docker仓库的应用
  16. 主机管理+堡垒机系统开发:strace命令及日志解析(五)
  17. ProtoType原型和__Proto__原型链的详解
  18. 【CSS】面试知识整理
  19. dede网站安全要做的四件事
  20. Poj3176 Cow Bowling (动态规划 数字三角形)

热门文章

  1. Unity-WIKI 之 AllocationStats(内存分配)
  2. MySQL的重装问题解决方法
  3. beanFactoory介绍
  4. 【转】【Asp.Net】asp.net(c#) 网页跳转
  5. [转]C#使用Log4Net记录日志
  6. 收集的User-Agent
  7. 可以这样去理解group by和聚合函数(转)
  8. Linux及安全——程序破解
  9. SDAccel-FPGA将带来至多25倍单位功耗性能提升
  10. 编译到底做了什么(***.c -&gt; ***.o的过程)