注意dp的定义以及为什么要排序
定义 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度， 注意必须被选取。
同上，先按照第一维进行排序，然后在第二维寻找LIS
排序的意义 ：通过对第一维进行排序，在动态规划求 的过程中，使得所有可能满足的前面的嵌套都已经求完， 不存在后面的信封能放在前面的任何一个信封里面 ，例如 [[5,4],[6,4],[6,7],[2,3]] ，最后一个信封能放在前面的信封里
和上面一模一样，复杂度也是
排序也 只用排第一维 ，因为 排序的意义在于遍历后面的箱子时确保前面的结果不会再改变了
经典的LIS问题.但从算法实现角度来看是不难的,可以有较简单的DP,O(n^2)
但数据量一大,TLE是必然的.
辅之以二分,可以优化至O(nlogn)
当然从你题目上可以看出,简单形式的也是可以胜任的.
下面这个是O(nlogn)
不懂可以再问,不过实践上你可以向任何一个ACMer或中学生OI选手请教.
#include<iostream>
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=0i<np[b[l]=i++]=b[l-1],ret+=(l>ret))
for (m=((l=1)+(r=ret))>>1l<=rm=(l+r)>>1)
if (_cp(a[b[m]],a[i]))
l=m+1
else
r=m-1
for (m=b[i=ret]ians[--i]=a[m],m=p[m])
return ret
}
int main(){
int n,Tcin>>T
while(T--&&cin>>n){
for (int i=0i<n&&cin>>a[i]++i)
int mlen=subseq(n,a,ans)
cout<<mlen<<endl
for (int i=0i<mlen++i)
if(i!=mlen-1)
cout<<ans[i]<<' '
else
cout<<ans[i]<<endl
cout<<endl}
}
