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 |
代码量大,不过效率不错,分享下我的代码。先后定义了两个类,重载了三个运算符,为了提高效率还用了快排。只不过代码太多了。 #include<stdio.h> class Place { public: int h; int row; int col; Place operator = (Place x) { h=x.h; row=x.row; col=x.col; return *this; } bool operator > (Place x) { return(h>x.h); } bool operator < (Place x) { return(h<x.h); } }; class Location { public: int hh; int count; }; void swap(Place &a,Place &b) { Place temp; temp=a; a=b; b=temp; } int partition(Place *a,int p,int r) { //划分算法 int i=p,j=r+1;Place x=a[p]; //将<=x的元素交换到左边区域 //将>=x的元素交换到右边区域 while(true) { while(a[++i]<x&&i<r); while(a[--j]>x); if(i>=j)break; swap(a[i],a[j]); } swap(a[j],a[p]); return j; } void quicksort(Place *a,int p,int r) { //随机化的快速排序算法 if(p<r) { int q=partition(a,p,r); quicksort(a,p,q-1);//对左半段排序 quicksort(a,q+1,r);//对右半段排序 } } int main() { int i,j,r,k,c,n,max=0,tmax,tmp,flag; Place pla[10003]; Location loc[103][103]; scanf("%d%d",&r,&c); n=r*c; k=0; for(i=0;i<=r+1;i++) { for(j=0;j<=c+1;j++) { if(i==0||i==r+1||j==0||j==c+1) { loc[i][j].hh=9999999; } else { scanf("%d",&loc[i][j].hh); pla[k].h=loc[i][j].hh; pla[k].row=i; pla[k++].col=j; } } } quicksort(pla,0,n-1); for(i=0;i<n;i++) { tmax=0; flag=0; if(loc[pla[i].row-1][pla[i].col].hh<loc[pla[i].row][pla[i].col].hh) {//上 flag=1; tmp=loc[pla[i].row-1][pla[i].col].count+1; tmax=tmax>tmp?tmax:tmp; } if(loc[pla[i].row+1][pla[i].col].hh<loc[pla[i].row][pla[i].col].hh) {//下 flag=1; tmp=loc[pla[i].row+1][pla[i].col].count+1; tmax=tmax>tmp?tmax:tmp; } if(loc[pla[i].row][pla[i].col-1].hh<loc[pla[i].row][pla[i].col].hh) {//左 flag=1; tmp=loc[pla[i].row][pla[i].col-1].count+1; tmax=tmax>tmp?tmax:tmp; } if(loc[pla[i].row][pla[i].col+1].hh<loc[pla[i].row][pla[i].col].hh) {//右 flag=1; tmp=loc[pla[i].row][pla[i].col+1].count+1; tmax=tmax>tmp?tmax:tmp; } if(flag==0) { tmax=loc[pla[i].row][pla[i].col].count=1; } loc[pla[i].row][pla[i].col].count=tmax; max=max>tmax?max:tmax; } printf("%d\n",max); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator