uva 10131 - Is Bigger Smarter?

题目

http://uva.onlinejudge.org/external/101/10131.html

输入是一些有序整数对

(a1,b1)
(a2,b2)
(a3,b3)

要求从中挑取一部分输出。 输出需要满足满足第一列严格递减,第二列严格递增,即 a(i) < a(i+1) && b(i+1) < b(i)

输出的序列可以不保持原先的相对顺序。求输出的序列的最大长度。

分析

这是一个与LIS相关的题目。我想套用之前的代码,在O(nlgn)的时间内解决这个问题。 关于LIS的讨论参见 http://www.sunchangming.com/blog/post/4583.html

首先,我的想法是,把输入的序列按照第一列排序,然后扔到我之前写好的LIS函数中求解(求LIS时只考虑b的值,不管a)。

可惜,失败了。因为第一列有可能重复。

(1,3)
(1,2)

的LIS的长度应该是1。如果LIS的时候不考虑第一列,会出错。

于是我把LIS的时候的comp函数换成了

 bool operator<(const elephant& r) const{
    return this->first < r.first && this->second > r.second;
 }

结果还是错了!这跟我采用的LIS算法有关。

假设输入为

A[0]={500,1}
A[1]={500,2000}
A[2]={600,1000}

在处理第二行的时候, 因为A[1] < A[0] == false ,所以我不能拿它来替换M[0]。并且 A[0] < A[1] == false,我也不能把它放在原来的LIS的末尾构成一个更长的LIS。综上所述,我只能在处理中把它丢弃。

结果是,在处理A[2]的时候遇到了同样的情况。

所以,要使我的算法能正常工作,

如果有A[1]<A[2] && !(A[0]<A[2]) 必须有 A[1] < A[0]

于是我最终这样:

排序的时候,两列都按照升序排

计算LIS的时候,对于第一列,只判断是否相等。

 bool operator<(const elephant& r) const{
    return this->first != r.first && this->second > r.second;
 }

如果把上式的不等号换成大于或者小于,都会出错。嗯……

虽然最终AC了,但是怎么证明我这么做是对的呢? 我还没想清楚。

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥