Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
计数排序按高度DP,0ms水过我也是醉了#include<cstdio> int c[10050]; bool e[10050]; int h[110][110],a[110][110]; int x[10050][150],y[10050][150],t,i,j,k,r,u,tx,ty,ans; int d[4]= {0,0,-1,+1},f[4]= {-1,+1,0,0}; int main() { scanf("%d%d",&r,&u); for(i=1; i<=r; i++) for(j=1; j<=u; j++) { scanf("%d",&t); h[i][j]=t; x[t][c[t]]=i; y[t][c[t]]=j; c[t]++; } for(i=0; i<10001; i++) { e[i]=1; for(j=0; j<c[i]; j++) { tx=x[i][j]; ty=y[i][j]; for(k=0; k<4; k++) if((!(e[h[tx+d[k]][ty+f[k]]]))&&(a[tx+d[k]][ty+f[k]]<=a[tx][ty])) a[tx+d[k]][ty+f[k]]=a[tx][ty]+1; } } for(i=1; i<=r; i++) for(j=1; j<=u; j++) if(a[i][j]>ans) ans=a[i][j]; printf("%d\n",ans+1); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator