luogu 1169 [ZJOI2007]棋盘制作 悬线dp
2024-08-28 08:28:57
悬线法,虽然得不到局部最优解,但是一定能得到全局最优解的算法,十分神奇~
#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;
}
最新文章
- 字典转换成NSString(NSJson)
- keepalived安装
- 转:RealThinClient (RTC)是什么?
- JSon_零基础_003_将Map集合对象转换为JSon格式的对象字符串,返回给界面
- SQL Server 2012 数据库备份
- 【原创】jQuery插件 - Booklet翻书特效教程(一) 一般设置
- 简洁 Abstract Factory模式(3.1)
- php笔记之GD库图片创建/简单验证码
- FindBugs的Bug类型及分析
- 表被占用住,提示资源正忙的处理方式。kill掉表的操作。
- Hadoop学习之常用命令
- jQuery Tags Input 插件显示选择记录
- Weka开发[4]-特征选择
- 7.21.01 if语句
- of_alias_get_id 函数与设备树中aliases节点的关系【转】
- shell从入门到精通进阶之一:Shell基础知识
- Ipython Notebook ipynb文件转化为Python脚本
- Linux下maven安装
- Asp.net中web.config配置文件详解(一)
- js对象(BOM部分/DOM部分)
热门文章
- php中的访问类型(public,private,protected)
- CentOS7安装配置redis5集群
- IDEA的常见的设置和优化(功能)
- According to MySQL 5.5.45+, 5.6.26+ and 5.7.6+ requirements SSL connection must be established by de
- JS-上下文练习
- vue学习(8)-过渡transition&;动画animate
- excel中的更新链接
- Java在常见的spring面试问题TOP50
- Python3 GUI:PyQt5环境搭建
- css 之内容溢出滚动,隐藏滚动条(解决火狐浏览隐藏不了滚动条问题)