POJ1050

给定一个矩阵,求和最大的子矩阵。

将每一列的值进行累加,枚举起始行和结束行,然后就可以线性优化了 复杂度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;
}

  

最新文章

  1. Unity Animator动画状态机 深入理解(三)二维混合树
  2. WPF 弹出UserControl
  3. php 执行程序分析
  4. [译]git init
  5. jsp_数据库的连接
  6. BZOJ 4052: [Cerc2013]Magical GCD
  7. C# 线程(六):定时器
  8. Linux C double linked for any data type
  9. java的单例设计模式
  10. Let it Bead
  11. 《python基础教程》笔记之 条件语句和循环语句
  12. 【转】Android源码学习(2)使用Git和Repo进行版本管理
  13. THP Transparent HugePages 相关知识与关闭
  14. mysql安装前的系统准备工作(转)
  15. centos主机信任
  16. JAVA常用API(Date、DateFormat、Calendar、System、Math、基本数据类型包装类)
  17. antd Tree组件中,自定义右键菜单
  18. 解决只读时ios下input光标问题
  19. 基于bootstrap-treeview做的一个漂亮的无限分类树层级联动菜单
  20. 解决微信小程序ios端滚动卡顿的问题

热门文章

  1. 如果由你来设计 12306.cn,你会怎么设计?
  2. MySQL-----操作练习
  3. 09-看图理解数据结构与算法系列(B树)
  4. AndroidSweetSheet:从底部弹出面板(1)
  5. CodeForces - 425E Sereja and Sets 题解
  6. 【最大流】Escape
  7. 食物(bzoj 3280)
  8. msp430入门编程01
  9. nyoj_10_skiing_201405181748
  10. P1547 Out of Hay 洛谷