POJ 1836 Alignment

这两天一直准备着校招，其实也没怎么准备。。。。好羡慕WY第一场校招就拿下offer。

说回正题，今天看了一会面试题。有一道老题LIS，求最长递增子序列。大概是大二的时候吧，就知道NlogN的算法，维护一个有序数组，二分查找当前数值在数组中的位置。

于是，就去POJ找了一题练练手，没错了，就是1836。

首先我题意就看错了。。。以为就是简单LCS，直接贴了代码。

题目大意是：有一队士兵，身高参差不齐，问你最少踢出几个人使队列符合队长的要求。

队长的要求大致是三种情况： （翻译的不好，直接分析了）
1.严格单调递增
2.严格单调递减
3.先严格单调递增，再严格单调递减。

我是对数组做了两遍LIS，再枚举情况3的递增终点和递减起点。我一开始还讨论了一下终点和起点是同一个人还是不同两个人，其实没必要，直接枚举就包含了！

Talk is cheap，just show the code:

POJ 1836 Alignment

778477 1836 Accepted 416K 32MS G++ 1672B 2013-09-15 21:02:24

#define N 1005
const int eps = 0.00001;
double a[N],lis[N];
int r[N],l[N],n;
int bin_search(int left,int right,double x)
{
    int mid;
    while(left <= right)
    {
        mid = left+(right-left)/2;
        if(lis[mid] > x) right = mid-1;
        else if(lis[mid] < x) left = mid+1;
        else return mid;
    }
    return left;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%lf",&a[i]);
        int index,len;
        len = 1;
        lis[0] = a[0];
        l[0] = 1;
        for(int i=1;i<n;i++)
        {
            if(a[i] > lis[len-1]) lis[len] = a[i],len++,l[i] = len;   //两个边界情况就不用二分找了
            else if(a[i] < lis[0]) lis[0] = a[i],l[i] = 1;       //直接维护就行
            else
            {
                index = bin_search(0,len,a[i]);
                lis[index] = a[i];
                if(index > len) len++;
                l[i] = index+1;
            }
        }
        lis[0] = a[n-1];
        r[n-1] = 1;
        len = 1;
        for(int i=n-2;i>-1;i--)
        {
            if(a[i] > lis[len-1]) lis[len] = a[i],len++,r[i] = len;
            else if(a[i] < lis[0]) lis[0] = a[i],r[i] = 1;
            else
            {
                index = bin_search(0,len,a[i]);
                lis[index] = a[i];
                if(index > len) len++;
                r[i] = index+1;
            }
        }
        int ans = -1;
        for(int i=0;i<n-1;i++)
            for(int j=i+1;j<n;j++)
                if(l[i]+r[j] > ans) ans = l[i]+r[j];
        printf("%d\n",n-ans);
    }
    return 0;
}

还有一点LIS常识，维护的lis数组并不一定是正确的最长递增子序列，而len是确定的最长递增子序列长度。

比如这组数据：
7
5 3 4 8 6 2 7

2 4 6 7 是维护的lis数组。
4 是最长递增子序列的长度。

正确的LIS数组应该为 3 4 6 7.

想得到正确的LIS数组，可以为每个数值附加一个pre前驱值。因为扫完一边数组后，lis数组最后的值一定是正确的。维护lis数组的时候，当插入的数值有前驱时，就记录一下他的前驱数值。 下面模拟一遍上面的数据。

5进lis，没有前驱，可以把前驱设为-1；LIS：（5）
3进lis，把5顶掉，同理没有前驱，设前驱为-1。LIS:（3）
4进lis，有前驱3。LIS：（3,4[3]）
8进lis，有前驱4。LIS：（3,4[3],8[4]）
6进lis，顶掉8，有前驱4。LIS：（3,4[3],6[4]）
2进lis，顶掉3，没有前驱。LIS：（2,4[3],6[4]）
最后一步，进7，有前驱6。LIS：（2,4[3],6[4],7[6]）
可以递归打印LIS，7->6->4->3 -1为递归出口。

以上就是完整的LIS了，NlogN求长度，递归打印LIS

第一次写的这么详细。

复制来自我的新浪博客(http://blog.sina.com.cn/s/blog_ad5e1c0c0101o5c0.html)