#include <iostream>

using namespace std;
int m,n;
struct node 
{
	int N;
	int l,r;
};
void copy(node &a,node &b)
{
	a.N=b.N;a.l=b.l;a.r=b.r;
}
int Partition(node a[],int low,int high)
{
    int pivotloc;
	copy(a[0],a[low]);
	pivotloc=a[low].N;
	while(low<high)
	{
		while(low<high&&a[high].N>=pivotloc)
			--high;
		if(low<high){
			copy(a[low++],a[high]);
		}
		while(low<high&&a[low].N<=pivotloc)
			++low;
		if(low<high)
		{
			copy(a[high--],a[low]);
		}
	}
	copy(a[low],a[0]);
	return low;
}
void QSort(node a[],int s,int t)
{   
    int pivotloc;

	if(s<t){
	 pivotloc=Partition(a,s,t);
	 QSort(a,s,pivotloc-1);    
	 QSort(a,pivotloc+1,t);
	}
}
void Quick_sort(node a[])
{
  QSort(a,1,m*n);

}
int  main()
{
	int **a,i,j,k=1,*visted;
	node *b;
	int c[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
	cin>>m>>n;
    a=new int*[m+2];
	for(i=0;i<m+2;i++)
		a[i]=new int[n+2];
	b=new node[m*n+1];
	visted=new int[m*n+1];
	for(i=1;i<=m*n;i++)
		visted[i]=1;
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
		{  
			b[k].N=a[i][j];
			b[k].l=i;
			b[k].r=j;
			k++;
		}	
	Quick_sort(b);
	int sum=0,count=1;
	node p;k=1;
	for(k=1;k<=m*n-sum;k++) 
	{  
    	if(visted[k])
		{
	     copy(p,b[k]);visted[k]=0;
	    for(i=k+1;i<=m*n;i++)
		{   
		    for(j=0;j<4;j++)
			if((p.l+c[j][0])>=1&&(p.l+c[j][0])<=m&&(p.r+c[j][1])>=1&&(p.r+c[j][1])<=n&&
				a[p.l+c[j][0]][p.r+c[j][1]]==b[i].N&&b[i].N>p.N)
			{  
			   count++;	
			   p.N=p.l=p.r=0;
			   copy(p,b[i]);
			   visted[i]=0;
			   break;
			}
		}
    	 if(count>sum)sum=count; 	 
		}
	count=1;
	}
	cout<<sum<<endl;
	return 0;
}

• 我自己什么数据都试过了；；并且都对，希望各位帮我找下特别点的数据。。。 (0) boys 2006-07-22 18:45:10
  • 然后把qsort() 改成用库函数的qsort() (0) sunmoonstar_love 2006-07-22 19:22:45
  • 你的做法是，先排序，然后按相邻关系找最长单调序列？ (0) sunmoonstar_love 2006-07-22 19:27:50
    • Re:解题思路 (172) boys 2006-07-23 11:24:00
• 用记忆化搜索好做 (1937) sunmoonstar_love 2006-07-22 19:16:22
  • Re:用记忆化搜索好做 (78) boys 2006-07-23 11:27:15