注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1057][ZJOI2007]棋盘制作  

2014-10-31 09:19:22|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1057: [ZJOI2007]棋盘制作

复习~
APIO时候学的东西,现在已经完全忘了QAQ
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N= 2000+10;
int n,m;
int map[N][N],h[N][N],l[N][N],r[N][N];
int scan(){int i=0;scanf("%d",&i);return i;}
inline bool can(int a,int b){return a>=0 && ((a^b)==1);}
int main(){
int i,j,a;char cc;
n = scan();m = scan();
for(i=0;i<=n+1;i++)
for(j=0;j<=m+1;j++)
map[i][j] = -1,r[i][j] = l[i][j] = m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
cc=' ';while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='1')map[i][j] = 1;
else map[i][j] = 0;
}
int tmp[N],ans[2]={};
tmp[0] = tmp[m+1] = 0;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(can(map[i][j-1],map[i][j])) tmp[j] = tmp[j-1]+1;
else tmp[j] = 1;
if(can(map[i-1][j],map[i][j])){
h[i][j] = h[i-1][j] + 1;
l[i][j] = min(l[i-1][j],tmp[j]);
}else{
h[i][j] = 1;
l[i][j] = tmp[j];
}
}
for(j=m;j;j--){
if(can(map[i][j+1],map[i][j]))tmp[j] = tmp[j+1]+1;
else tmp[j] = 1;
if(can(map[i-1][j],map[i][j]))
r[i][j] = min(r[i-1][j],tmp[j]);
else
r[i][j] = tmp[j];
//updeate ans
a = min(h[i][j],r[i][j]+l[i][j]-1);
ans[0] = max(ans[0],a*a);
ans[1] = max(ans[1],h[i][j]*(r[i][j]+l[i][j]-1));
}
}
printf("%d\n%d\n",ans[0],ans[1]);
return 0;
}

题解:
经典算法:悬线法求最大子矩阵
这里稍稍变形了一下,如果只有颜色间隔才能移动/把悬线连上去
没啥好说的不懂看代码吧
  评论这张
 
阅读(16)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017