悬线法,虽然得不到局部最优解,但是一定能得到全局最优解的算法,十分神奇~

#include <cstdio>
#include <algorithm>
#define N 2003
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,m,ans1,ans2;
int v[N][N],l[N][N],r[N][N],up[N][N],len[N][N];
int main()
{
int i,j;
// setIO("input");
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j)
scanf("%d",&v[i][j]),l[i][j]=r[i][j]=j, up[i][j]=1,len[i][j]=1;
}
for(i=1;i<=n;++i)
{
for(j=2;j<=m;++j) if(v[i][j]!=v[i][j-1]) l[i][j]=l[i][j-1];
for(j=m-1;j>=1;--j) if(v[i][j]!=v[i][j+1]) r[i][j]=r[i][j+1];
}
for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j)
{
if(i>1 && v[i][j]!=v[i-1][j])
{
l[i][j]=max(l[i][j], l[i-1][j]);
r[i][j]=min(r[i][j], r[i-1][j]);
up[i][j]=up[i-1][j]+1;
}
ans1=max(ans1, up[i][j]*(r[i][j]-l[i][j]+1));
}
}
for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j)
{
if(i>1&&j>1&&v[i][j]!=v[i][j-1]&&v[i][j]!=v[i-1][j]&&v[i][j]==v[i-1][j-1])
{
len[i][j]=min(len[i][j-1], min(len[i-1][j], len[i-1][j-1]))+1; }
}
}
for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j) ans2=max(ans2, len[i][j]*len[i][j]);
}
printf("%d\n%d\n",ans2,ans1);
return 0;
}

  

最新文章

  1. 字典转换成NSString(NSJson)
  2. keepalived安装
  3. 转:RealThinClient (RTC)是什么?
  4. JSon_零基础_003_将Map集合对象转换为JSon格式的对象字符串,返回给界面
  5. SQL Server 2012 数据库备份
  6. 【原创】jQuery插件 - Booklet翻书特效教程(一) 一般设置
  7. 简洁 Abstract Factory模式(3.1)
  8. php笔记之GD库图片创建/简单验证码
  9. FindBugs的Bug类型及分析
  10. 表被占用住,提示资源正忙的处理方式。kill掉表的操作。
  11. Hadoop学习之常用命令
  12. jQuery Tags Input 插件显示选择记录
  13. Weka开发[4]-特征选择
  14. 7.21.01 if语句
  15. of_alias_get_id 函数与设备树中aliases节点的关系【转】
  16. shell从入门到精通进阶之一:Shell基础知识
  17. Ipython Notebook ipynb文件转化为Python脚本
  18. Linux下maven安装
  19. Asp.net中web.config配置文件详解(一)
  20. js对象(BOM部分/DOM部分)

热门文章

  1. php中的访问类型(public,private,protected)
  2. CentOS7安装配置redis5集群
  3. IDEA的常见的设置和优化(功能)
  4. According to MySQL 5.5.45+, 5.6.26+ and 5.7.6+ requirements SSL connection must be established by de
  5. JS-上下文练习
  6. vue学习(8)-过渡transition&amp;动画animate
  7. excel中的更新链接
  8. Java在常见的spring面试问题TOP50
  9. Python3 GUI:PyQt5环境搭建
  10. css 之内容溢出滚动,隐藏滚动条(解决火狐浏览隐藏不了滚动条问题)