快排＋双链表＋动态规划
#include<iostream>
#include<cmath>
#define Max 100000000
using namespace std;
struct link
{
	int next;
	int pre;
}*write;
int N,D,Last=0;
int *temp,*best,**Data;
int part(int *a,int p,int r)
{
	int i=p,j=r+1;
	int x=a[p];
	while(true){
		while(a[++i]<x);
		while(a[--j]>x);
		if(i>=j)	break;
		swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}
void quicksort(int *a,int p,int r)
{
	if(p<r){
		int q=part(a,p,r);
		quicksort(a,p,q-1);
		quicksort(a,q+1,r);
	}
}
int position(int *b)
{
	int i,j,k=1;
	bool flag;
	for(j=0;j<D;j++){
		if(Data[0][j]>=b[j])
			return -1;
	}
	i=0;
	while(write[i].next!=Max){
		i=write[i].next;
		flag=true;
		for(j=0;j<D;j++){
			if(Data[i][j]<b[j])
				flag=false;
		}
		if(flag==false)	k++;
		else break;
	}
	return k;
}
void readdata()
{
	Data=new int*[N+1];
	temp=new int[D];
	best=new int[N+1];
	write=new link[N+1];
	int i,j,k;
	for(j=0;j<=N;j++)
		write[j].next=write[j].pre=Max;
	for(i=0;i<=N;i++){
		Data[i]=new int[D];
		best[i]=0;
		for(j=0;j<D;j++){
			cin>>temp[j];
		}
		quicksort(&temp[0],0,D-1);
		for(j=0;j<D;j++)
			Data[i][j]=temp[j];
		if(i==1){
			write[0].next=i;
			write[0].pre=-1;
			write[i].pre=0;
		}
		if(i>1){//插入排序
			k=position(&temp[0]);
			if(k!=-1&&k>=1){
				j=0;
				int count=1;
				while(write[j].next!=Max){
					j=write[j].next;
					count++;
					if(count==k) break;
				}
				int tempdata=write[j].next;
				write[j].next=i;
				write[i].next=tempdata;
				write[i].pre=j;
				if(tempdata!=Max)
					write[tempdata].pre=i;
				else
					Last=i;
			}
		}
	}
}
int ok(int *a,int *b)
{
	int i;
	for(i=0;i<D;i++){
		if(a[i]>b[i])
			return 0;
	}
	return 1;
}
void Dp()
{
	int i=Last,j;
	while(i!=-1){
		j=write[i].next;
		while(j!=Max){
			if(ok(&Data[i][0],&Data[j][0])==1&&best[i]<best[j]+1){
				best[i]=best[j]+1;
			}
			j=write[j].next;
		}
		i=write[i].pre;
	}
}
void print()
{
	if(best[0]>0)
		cout<<best[0]<<endl;
	else
		cout<<"Please look for another gift shop!"<<endl;
}
int main()
{
	while(cin>>N>>D){
		readdata();
		Dp();
		print();
	}
	return 0;
}

• Re:高. (15) Morpheus 2006-09-30 15:21:46
• Re:Sort+Sort+Dp,That's is Ac! (18) peter_pan 2006-10-03 16:32:59
• Re:Sort+Sort+Dp,That's is Ac! (2056) busycai 2006-10-03 16:35:23
  • Just LCS~ (2218) busycai 2006-10-03 16:39:16