求一个整数序列的最长递增子序列。 输入的第一行是一个正整数 n，表示测试例个数。接下来几行是 n 个测试例的数据，每个测 试例的数据由两行组成，其中第一行为一个正整数 k (k<=500)，表示整数序列的长度，第二 行给出整数序列，整数之间用一个空格隔开。（设给出的每个整数序列的最长递增子序列都 是唯一的.对于每个测试例输出两行，第一行为最长递增子序列的长度，第二行为最长递增 子序列，整数之间用一个空格隔开。两个测试例的输出数据之间用一个空行隔开。 例如 输入： 2 5 3 1 4 2 3 6 1 3 9 5 2 6 输出： 3 1 2 3 4 1 3 5 6 提问者： 蝶破焰澈 - 三 级 最佳答案 经典的 LIS 问题. 但从算法实现角度来看是不难的,可以有较简单的 DP,O(n^2) 但数据量一大,TLE 是必然的. 辅之以二分,可以优化至 O(nlogn); 当然从你题目上可以看出,简单形式的也是可以胜任的. 下面这个是 O(nlogn); 不懂可以再问,不过实践上你可以向任何一个 ACMer 或中学生 OI 选手请教. #include using namespace std; #define _cp(a,b) ((a)<(b)) int ans[501],a[501]; int subseq(int n,int* a,int* ans){ int b[501],p[501],i,l,r,m,ret=0; for (i=0;iret)) for (m=((l=1)+(r=ret))>>1;l<=r;m=(l+r)>>1) if (_cp(a[b[m]],a[i])) l=m+1; else r=m-1; for (m=b[i=ret];i;ans[--i]=a[m],m=p[m]); 

2 return ret; } int main(){ int n,T;cin>>T; while(T--&&cin>>n){ for (int i=0;i>a[i];++i); int mlen=subseq(n,a,ans); cout< using namespace std; #define N 501 main() { int i,j,k,n,max; int a[N],len[N],next[N]; cin>>n; while(n--) { cin>>k; for(i=0;i>a[i]; for(i=0;i=0;--i) { for(max=0,j=i+1;j

cout< #include using namespace std; #define num_count 10 int num_in[num_count] = {1,5,0,4,8,6,7,2,9,3}; int num_out[num_count]; int result[num_count]; int max_count = 0; // void combine(int level , int pos ) { for(int i = pos ; i < num_count ; i++) { num_out[level] = num_in[i]; if(level && num_out[level-1] > num_out[level])continue; if(level+1 > max_count)memcpy(result , num_out , (max_count=level+1)*sizeof(int)); combine(level + 1 , i + 1 ); } } void main() { combine(0 , 0); cout << max_count << endl; copy(result,result+max_count,ostream_iterator(cout," ")); }