題意就是求最長上升子序列，且必須用nlogn的dp算法。
技巧：設(shè)置一個(gè)數(shù)組a[i]
存放所有長度為i的上升子序列中最小的末元素值，比如說只有兩個(gè)長度為3的上升子序列123和124，那么a[3]中存放的就是3（末元素3<4）
那么當(dāng)來一個(gè)新數(shù)data時(shí)，如果它的值大于最長長度的末元素的值（即a[ans]），則ans++；且a[ans]=data;
否則，通過二分查找（數(shù)組a中的元素為遞增），將最接近data且大于data的那個(gè)元素更新為data，既最小的大于它的數(shù)。
例如1,5,3,4,之后來個(gè)2，a[1]=1,a[2]=3,a[3]=4;則更新a[2]=2;
由于二分查找復(fù)雜度為log(n)，外圍為n,總的復(fù)雜度為nlogn
代碼。
#include <stdio.h>
int res[40000];
int binSearch(int left, int right, int num)//找到最小的大于等于它的數(shù)
{
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);//找到最小的大于它的數(shù)
res[pos+1] = num;
}
}
printf("%d\n", tot);
}
return 0;
}
posted on 2009-07-12 15:46
luis 閱讀(541)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
動(dòng)態(tài)規(guī)劃