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 |
动态规划就可以了In Reply To:郁闷,为什么总是超时呢? Posted by:fzk at 2004-05-25 20:13:49 > #include"iostream.h" > > int high[102][102]; > int path[102][102]; > int x[10700]; > > inline int cmp(int i) > {return high[x[i]%101][x[i]/101];} > > > > > void quicksort(int n,int m) > {int s; > int i=n+1,j=m; > if(n>=m)return; > > while(i<j) > { > while(cmp(n)>=cmp(i)&&i<j)i++; > while(cmp(n)<=cmp(j)&&j>i)j--; > > if(cmp(i)>cmp(j)){s=x[i];x[i]=x[j];x[j]=s;} > } > > if(cmp(i)>cmp(n))i--; > > s=x[i];x[i]=x[n];x[n]=s; > quicksort(n,i-1); > quicksort(i+1,m); > } > > > > > > int main() > {int n,m,i,j,h,a,b,t,best; > cin>>n>>m; > for(i=0;i<=n+1;i++)path[i][0]=path[i][m+1]=0; > > for(i=0;i<=m+1;i++)path[0][i]=path[n+1][i]=0; > > > h=0; > for(i=1;i<=n;i++) > for(j=1;j<=m;j++) > {cin>>high[i][j];path[i][j]=0;x[h++]=i+j*101;} > > quicksort(0,m*n-1); > j=m*n-1; > best=1; > > > for(h=0;h<m*n;h++) > {a=x[j]%101; > b=x[j]/101; > j--; > t=0; > if(high[a-1][b]>high[a][b]&&path[a-1][b]>t)t=path[a-1][b]; > if(high[a+1][b]>high[a][b]&&path[a+1][b]>t)t=path[a+1][b]; > if(high[a][b-1]>high[a][b]&&path[a][b-1]>t)t=path[a][b-1]; > if(high[a][b+1]>high[a][b]&&path[a][b+1]>t)t=path[a][b+1]; > path[a][b]=t+1; > if(best<path[a][b])best=path[a][b]; > } > cout<<best<<endl; > > return 1; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator