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)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 回溯算法 回溯法:也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规模开始逐步求解出可能的答案,并...
    fredal阅读 13,763评论 0 89
  • 第5章 引用类型(返回首页) 本章内容 使用对象 创建并操作数组 理解基本的JavaScript类型 使用基本类型...
    大学一百阅读 3,272评论 0 4
  • 国家电网公司企业标准(Q/GDW)- 面向对象的用电信息数据交换协议 - 报批稿:20170802 前言: 排版 ...
    庭说阅读 11,196评论 6 13
  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 31,780评论 18 399
  • 在饼与饼之间跳跃,比穿着裙子拍文艺片,还过瘾。 上一秒我还在纠结着我这直爽的性格不知道得罪了多少人,下一秒就收到你...
    二个姿娘阅读 437评论 0 0