POJ1050 To the Max 最大子矩阵
2024-08-30 20:28:49
给定一个矩阵,求和最大的子矩阵。
将每一列的值进行累加,枚举起始行和结束行,然后就可以线性优化了 复杂度O(n^3)
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int N=301,M=301;
const int INF=0x3fffffff;
int sum[N][M],arr[M];
int find_max(int a[N][M],int n,int m)
{
if(n==0||m==0)return 0;
int i,j,up,down, ret=-INF;
memset(sum,0,sizeof(sum));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
sum[i][j]=sum[i-1][j]+a[i][j];
arr[0]=0;
for(up=1;up<=n;up++)
for(down=up;down<=n;down++)
{
for(i=1;i<=m;i++)
arr[i]=arr[i-1]+(sum[down][i]-sum[up-1][i]);
int mini=0;
for(i=1;i<=m;i++)
{
ret=max(ret,arr[i]-mini);
mini=min(mini,arr[i]);
}
}
return max(0,ret);
} int main()
{freopen("t.txt","r",stdin);
int n;
while(scanf("%d",&n)!=EOF)
{
int num[N][M];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&num[i][j]);
printf("%d\n",find_max(num,n,n));
}
return 0;
}
最新文章
- Unity Animator动画状态机 深入理解(三)二维混合树
- WPF 弹出UserControl
- php 执行程序分析
- [译]git init
- jsp_数据库的连接
- BZOJ 4052: [Cerc2013]Magical GCD
- C# 线程(六):定时器
- Linux C double linked for any data type
- java的单例设计模式
- Let it Bead
- 《python基础教程》笔记之 条件语句和循环语句
- 【转】Android源码学习(2)使用Git和Repo进行版本管理
- THP Transparent HugePages 相关知识与关闭
- mysql安装前的系统准备工作(转)
- centos主机信任
- JAVA常用API(Date、DateFormat、Calendar、System、Math、基本数据类型包装类)
- antd Tree组件中,自定义右键菜单
- 解决只读时ios下input光标问题
- 基于bootstrap-treeview做的一个漂亮的无限分类树层级联动菜单
- 解决微信小程序ios端滚动卡顿的问题