lis.cpp

来自「ACM LIS.cpp help you to let UVa Judge to」· C++ 代码 · 共 80 行

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define max 200000

template <class DataType>
class LIS{
public:
	int size;
	DataType X[max];
private:
	int index[max];
	int length[max];
	DataType Lis[max];
	int LisLength;
public:
	LIS(){};
	void Operation(){
		
		int i,j;
		int ptr,len;
		
		index[0] = -1;
		length[0] = 1;
		
		for(i=1;i<size;i++){
			
			len = 0;
			ptr = -1;
			
			for(j=0;j<i;j++)
				if(X[j] < X[i] && length[j] > len){
					len = length[j];
					ptr = j;
				}
				
			length[i] = len + 1;
			index[i] = ptr;
		}
		
		len = 0;
		ptr = -1;
		for(i=0;i<size;i++)
			if(length[i] > len){
				len = length[i];
				ptr = i;
			}
			
		LisLength = len;
		for(i=len-1;i>=0;i--){
			Lis[i] = X[ptr];
			ptr = index[ptr];
		}
		
		for(i=0;i<len;i++)
			printf("%d ",Lis[i]);
	};
};

int main(){
	
	LIS<int> lis;
	lis.size = 11;
	lis.X[0] = 66;
	lis.X[1] = 92;
	lis.X[2] = 123;
	lis.X[3] = 31;
	lis.X[4] = 83;
	lis.X[5] = 53;
	lis.X[6] = 48;
	lis.X[7] = 17;
	lis.X[8] = 9;
	lis.X[9] = 57;
	lis.X[10] = 75;
	lis.Operation();
	
	return 0;
}