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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1567][JSOI2008]Blue Mary的战役地图  

2015-01-02 15:46:11|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1567: [JSOI2008]Blue Mary的战役地图

顺便做一下同一年的题……
这道还挺水
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 50+10;
int n,m;
int tmp[2][N][N];
short map[N][N];
int up[N],left[N],right[N],ld[N],rd[N];
int scan(){int i=0;scanf("%d",&i);return i;}
void makegraph(int dx,int dy){
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
int x,y;
x = i+dx;y = j+dy;
if(!(1<=x&&x<=n&&1<=y&&y<=n))map[i][j] = 0;
else map[i][j] = (tmp[0][i][j] == tmp[1][x][y]);
}
}
int main(){
int i,j,dx,dy,ans=0;
n = scan();
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
tmp[0][i][j] = scan();
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
tmp[1][i][j] = scan();
for(dx=-n +1;dx<=n -1;dx++)
for(dy=-n +1;dy<=n -1;dy++){
makegraph(dx,dy);
for(j=1;j<=n;j++)up[j] = 0,ld[j] = rd[j] = n*2;
for(i=1;i<=n;i++){
for(j=n;j;j--)
if(map[i][j])right[j] = right[j+1]+1;
else right[j] = 0;
for(j=1;j<=n;j++)
if(map[i][j]){
up[j]++;left[j] = left[j-1]+1;
ld[j] = min(ld[j],left[j]);
rd[j] = min(rd[j],right[j]);
int tmp = min(up[j],ld[j]+rd[j]-1);
if(tmp > ans)ans = tmp;
}else up[j] = left[j] = 0,ld[j]=rd[j]=n*2;
}
}
printf("%d\n",ans);
return 0;
}

题解:
悬线法求最大子矩阵。
首先枚举一个dx,dy表示两个矩阵的偏移量,然后根据每个位置是否相同构造一个01矩阵
最后在用悬线法就得到答案了……
时间复杂度O(n^4)
  评论这张
 
阅读(43)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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