POJ1836-LIS变形

 

给出一个序列，求其最大的先递增后递减序列。采用二分实现，否则会超时，本题的二分很巧妙。

注意理解

    #include<iostream>
    using namespace std;
    #define MAXSIZE 1010
    #define MAX(a,b) (a>b?a:b)
    double a[MAXSIZE];
    double dp[MAXSIZE];
    int n;
    int tans1,tans2;

    int bin_search(int end,double k)//这里写成int k wa了无数次！！
    {
    	int l=1;
    	int r=end;
    	int mid;
    	while(l<=r)
    	{
    		mid=(l+r)/2;
    		if(k>dp[mid])
    		{
    			l=mid+1;
    		}
    		else
    		{
    			r=mid-1;
    		}
    	}
    	return l;
    }


    int lis(int x)
    {
    	memset(dp,0,sizeof(dp));
    	
    	int i,j,k;
    	//升序列 起点为0 终点为x [0,x];
    	dp[0]=0;
    	int cnt=0;
    	//本题需要采用二分查找法，否则会超时。
    	//方法：从起点开始，将遍历到到的元素放入一个数组中，并且维持这个数组
    	//的递增性质，那么在遍历完以后，这个数组中的长度就是以它为终点的递增子序列长度
    	for( i=0;i<=x;i++)
    	{
    		if(a[i]>dp[cnt])
    		{
    			dp[++cnt]=a[i];
    		}
    		else
    		{
    			int pos=bin_search(cnt,a[i]);
    			dp[pos]=a[i];
    		}
    	}
    	tans1=cnt;
    	//降序列 起点为x+1 终点为n-1 [x+1,n-1]
    	memset(dp,0,sizeof(dp));
    	cnt=0;
    	dp[0]=0;
    	for( i=n-1;i>=x+1;i--)
    	{
    		if(a[i]>dp[cnt])
    		{
    			dp[++cnt]=a[i];
    		}
    		else
    		{
    			int pos=bin_search(cnt,a[i]);
    			dp[pos]=a[i];
    		}
    	}
    	tans2=cnt;
    	
    	return tans1+tans2;
    }


    int slove()
    {
    	int smaxn=-1;
    	for(int i=0;i<n;i++)
    	{
    		smaxn=MAX(smaxn,lis(i));//	枚举起点
    	}
    	return smaxn;
    }

    int main()
    {
    	
    	while(scanf("%d",&n)!=EOF)
    	{	
    		//scanf("%d",&n);
    		for(int i=0;i<n;i++)
    		{
    			scanf("%lf",&a[i]);
    		}
    		
    		printf("%d\n",n-slove());
    	}
    	return 0;
    }