| ||||||||||
| 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