首页 > 代码库 > HDU1505(HDU1506的加强版)
HDU1505(HDU1506的加强版)
昨天打 CF又跪了,最近睡不好睡不好睡不好~感觉整个人都累傻了,根本无办法写下去,仅仅写了一题签到题就跪了orz..从未试过这么悲剧。
今天早上凭着我的意念(“怨念”),七点又起来了!我已经连续好多天七点自动起来(不是自然醒,是意念,是意念....),刷啊刷啊刷dp.
今天刷的是昨天的加强版,实际上就多了一个for循环,和做高度处理,不直到是不是正解( ╮(╯▽╰)╭ ),但是AC就好了...
经过多次调试我的shell脚本,这个acm.sh算是比较稳定了,还差一个自动提交机啊!我的肉不够多啊,人肉提交很累。
看到我的开始时间是07:41:44,因为我改了一下我的脚本,大概就是自动在hdu或者poj扒下测试数据,生成了文件in.txt,out.txt,以及自动生成带有ifndef什么的。
改.vimrc改到有小小感觉了,等我的机器人自动提交,我就可以共享到github,再写一篇关于我的acm.sh~不知道大家刷ACM的时候是不是特别蛋疼做很多无谓的工作~(比如每次拍数据!),我把我能想到可以机器人弄的都弄上去, O(∩_∩)O哈哈~
好吧,讲回题目,题目意思就是在一个方阵上找到最大的子矩阵,即全部标记为F的最大子矩阵,之后输出子矩阵F的个数*3.
思路就是,对每行构造高度矩阵(我是自顶向下的,比如 (R F F ;R F R),这样做到的矩阵为(0,2,1;0,1,0),有了高度,对每行做昨天的1506,then output!
/*********************************************************** > OS : Linux 3.2.0-60-generic #91-Ubuntu > Author : yaolong > Mail : dengyaolong@yeah.net > Time : 2014年06月02日 星期一 07:41:44 **********************************************************/ #include<iostream> #include<cstdio> #include<string> #include<cstring> using namespace std; int h[1005][1005]; char mp[1005][1005]; int lt[1005],rt[1005]; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif int T,n,m; scanf(" %d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++){ scanf(" %c",&mp[i][j]); } } for(int j=1;j<=m;j++){ h[0][j]=0; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(mp[i][j]=='R'){ h[i][j]=0; }else{ h[i][j]=h[i-1][j]+1; } } } /* for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ printf("%d",h[i][j]); } puts(""); }*/ int mmax=0,t; for(int i=1;i<=n;i++){ lt[1]=1;rt[m]=m; for(int j=2;j<=m;j++){ t=j; while(t>1&&h[i][j]<=h[i][t-1]) t=lt[t-1]; lt[j]=t; } for(int j=m-1;j>=1;j--){ t=j; while(t<m&&h[i][j]<=h[i][t+1]) t=rt[t+1]; rt[j]=t; } for(int j=1;j<=m;j++){ mmax=max(mmax,h[i][j]*(rt[j]-lt[j]+1)); } } printf("%d\n",mmax*3); } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。