题意就是求最长上升子序列，且必须用nlogn的dp算法。
技巧：设置一个数组a[i]
存放所有长度为i的上升子序列中最小的末元素值，比如说只有两个长度为3的上升子序列123和124，那么a[3]中存放的就是3（末元素3<4）
那么当来一个新数data时，如果它的值大于最长长度的末元素的值（即a[ans]），则ans++；且a[ans]=data;
否则，通过二分查找（数组a中的元素为递增），将最接近data且大于data的那个元素更新为data，既最小的大于它的数。
例如1,5,3,4,之后来个2，a[1]=1,a[2]=3,a[3]=4;则更新a[2]=2;
由于二分查找复杂度为log(n)，外围为n,总的复杂度为nlogn
代码。
#include <stdio.h>
int res[40000];
int binSearch(int left, int right, int num)//找到最小的大于等于它的数
{
while(left <= right)
{
int mid=(left + right)/2;
if(res[mid]<num)
left=mid+1;
else
right=mid-1;
}
return right;
}
int main()
{
//freopen("s.txt","r",stdin);
// freopen("key.txt","w",stdout);
int t, n, num;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &n, &num);
res[0]=num;
int tot = 1;
for(int i=1;i<n;++i)
{
scanf("%d", &num);
if(num>=res[tot-1])
res[tot++]=num;
else
{
int pos=binSearch(0,tot-1,num);//找到最小的大于它的数
res[pos+1] = num;
}
}
printf("%d\n", tot);
}
return 0;
}
posted on 2009-07-12 15:46
luis 阅读(516)
评论(0) 编辑 收藏 引用 所属分类:
动态规划