首页 > 代码库 > 引水入城——重新做一遍，原来真的水
引水入城——重新做一遍，原来真的水
去年第一次做硬是做了两三天都没过，我也不记得我当时到底是用了什么傻逼做法，总之最后三个点就是超时。今年上半年，大概五个月前又做了一次，最后看了题解。刚因为打了关押罪犯，就重做了一遍这题，总算没有以前那种折磨的感觉了。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int N=512,ax[]={1,-1,0,0},ay[]={0,0,1,-1}; 5 struct node{int l,r;}; 6 int n,m,cap,res=1,mxv,gr[N][N],f[N]; 7 bool vis[N][N]; 8 node seg[N][N]; 9 void dfs(int x,int y){10 if(vis[x][y])return;11 vis[x][y]=true;12 for(int i=0;i<4;i++){13 int nx=x+ax[i],ny=y+ay[i];14 if(nx>n||nx<1||ny>m||ny<1||gr[nx][ny]>=gr[x][y])continue;15 dfs(nx,ny);16 seg[x][y].l=min(seg[x][y].l,seg[nx][ny].l);17 seg[x][y].r=max(seg[x][y].r,seg[nx][ny].r);18 }19 }20 int main(){21 cin>>n>>m;22 for(int i=1;i<=n;i++)23 for(int j=1;j<=m;j++)24 scanf("%d",&gr[i][j]);25 for(int i=1;i<=n;i++)26 for(int j=1;j<=m;j++)27 if(i!=n)seg[i][j].l=N,seg[i][j].r=0;28 else seg[i][j].l=seg[i][j].r=j;29 for(int i=1;i<=m;i++)dfs(1,i);30 for(int i=1;i<=m;i++)cap+=!vis[n][i];31 if(cap){32 cout<<0<<endl<<cap<<endl;33 return 0;34 }35 for(int i=1;i<=m;i++)36 for(int j=seg[1][i].l;j<=seg[1][i].r;j++)37 if(f[j]>f[seg[1][i].l-1]||!f[j])38 f[j]=f[seg[1][i].l-1]+1;39 cout<<1<<endl<<f[m]<<endl;40 return 0;41 }
Vijos 109ms 另外，同样代码同样OJ 用iostream 输入是222ms ，scanf 居然快那么多。再其它OJ（其实也就是CodeVS） 上的耗时差距也都足足有一百毫秒，这还只是二十五万的数据啊。
引水入城——重新做一遍，原来真的水
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。