【poj1050】 To the Max
2024-08-28 19:34:22
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;
}
最新文章
- Apache Rewrite匹配问号的问题
- .html()和.text()的区别
- Apache2.4.6 添加虚拟主机
- HLS视频点播&;直播初探
- CentOS 下用的是lnmp 的包配置Nginx 下的CI伪静态(搞爽了)
- Quoted-printable 编码介绍、编码解码转换
- 未能加载文件或程序集&ldquo;XXX&rdquo;或它的某一个依赖项。试图加载格式不正确的程序。
- angular2 的依赖注入
- DB天气 Alpha版使用说明
- 转:C语言宏定义时#(井号)和##(双井号)的用法
- 冒泡排序java
- emacs quick open and jump file (or buffer) which name is current word
- 你需要了解的高可用方案之使用keepalived搭建双机热备一览
- 9、Libgdx的输入处理
- docker简单介绍----docker仓库的应用
- 主机管理+堡垒机系统开发:strace命令及日志解析(五)
- ProtoType原型和__Proto__原型链的详解
- 【CSS】面试知识整理
- dede网站安全要做的四件事
- Poj3176 Cow Bowling (动态规划 数字三角形)
热门文章
- Unity-WIKI 之 AllocationStats(内存分配)
- MySQL的重装问题解决方法
- beanFactoory介绍
- 【转】【Asp.Net】asp.net(c#) 网页跳转
- [转]C#使用Log4Net记录日志
- 收集的User-Agent
- 可以这样去理解group by和聚合函数(转)
- Linux及安全——程序破解
- SDAccel-FPGA将带来至多25倍单位功耗性能提升
- 编译到底做了什么(***.c ->; ***.o的过程)