http://acm.hdu.edu.cn/showproblem.php?pid=1257这道题要求最长递增子序列的长度，用二分+DP可求的。
#include <iostream>
using namespace std;
int result[30005]; //用于保存长度为i时的哨兵值
int bisearch(int a[],int lenth,int h) //二分查找插入的位子，如h存在，则返回原位置，既不做改变，否则返回比h大的位子
{
int i=0,j=lenth-1,mid;
while(i<=j)
{
mid=(i+j)/2;
if(a[mid]==h)
return mid;
if(a[mid]>h)
j=mid-1;
else
i=mid+1;
}
return i;
}
int main()
{
int n,h,lenth,pos;
while(scanf("%d",&n)!=EOF) //注意写上EOF，否则超时
{
result[0]=30005; //初始化最大，第一次执行的是插入操作
lenth=1;
while(n--)
{
scanf("%d",&h);
if(h>result[lenth-1]) //如果h比排头的大，则将h作为新的排头，长度增加，注意是>不是>=，
//如果有=则表示非递减序列，与题意不符
result[lenth++]=h;
else //否则进行插入操作，将比h大一点的数覆盖，不影响结果
{
pos=bisearch(result,lenth,h);
result[pos]=h;
}
}
printf("%d\n",lenth);
}
return 0;
}posted on 2011-07-31 20:06
大大木马 阅读(466)
评论(0) 编辑 收藏 引用