Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

动态规划就可以了

Posted by Alpha at 2004-05-25 21:39:15 on Problem 1088
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator