题意很简单,给定一个N*N的大矩阵,求其中数值和最大的子矩阵。

一开始找不到怎么DP,没有最优子结构啊,后来聪哥给了我思路,化成一维,变成最大连续和即可。为了转化成一维,必须枚举子矩阵的宽度,通过预处理的suffix可以很快计算出每一列某一段的和,然后进行一维DP即可。。总复杂度为 O(N^3);

 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int mat[110][110];
int suffix[110][110];
int n;
int main()
{
while (scanf("%d",&n)!=EOF)
{
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
scanf("%d",&mat[i][j]);
}
}
//memset(suffix,0,sizeof suffix);
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
suffix[i][j]=suffix[i][j-1]+mat[i][j];
}
}
int d=0;
int ans=-(1<<30); //因为有负值,所以初始要为-inf,一开始设置为0,UVA过了,URAL没过,大概是因为URAL里面就出现了负最大值吧
for (int i=1; i<=n; i++)
{
for (int j=i; j<=n; j++)
{
d=0;
for (int k=1; k<=n; k++)
{
int tmp=suffix[k][j]-suffix[k][i-1];
d+=tmp;
ans=max(d,ans);
if (d<0) d=0;
}
}
}
printf("%d\n",ans);
}
return 0;
}

  

  

最新文章

  1. 命令查询网站是否开启CDN加速
  2. es_Linux
  3. DirectX 9 SDK安装后在vs2010里编译BaseClasses出错问题解决方法
  4. C++编程开发学习的50条建议(转)
  5. 算法系列7《CVN》
  6. win7硬盘安装Ubuntu12.04 64位时显示Error 15: File not found.
  7. 浅谈JNDI的使用
  8. window批量-6 rem
  9. PATH menu
  10. 阿里JAVA开发手册零度的思考理解(二)
  11. RobotFramework下的http接口自动化post关键字的使用
  12. &amp;amp;
  13. 华大单片机开发板HC32F030上手入门
  14. group by查询每组时间最新的一条记录
  15. js篇之对象数据属性与存取器属性
  16. 【九天教您南方cass 9.1】 14 坐标数据的纠正
  17. ReactNative小笔记
  18. 新节点在线加入PXC
  19. 通过eclipse创建项目
  20. delphi中如何控制listview的每行的颜色

热门文章

  1. 开源Web测试工具介绍
  2. PCA主成分分析算法的数学原理推导
  3. PHP连数据库生成数据字典
  4. CrossOriginFilter
  5. DEDE后台升级后不显示编辑器
  6. 部署 Helm【转】
  7. other#docker
  8. 机器学习(ML)八之正向传播、反向传播和计算图,及数值稳定性和模型初始化
  9. dmp文件自动分析
  10. 十七、React路由嵌套:头部导航+侧边导航