UVA 最大递增子序列(LIS)相关题目总结

基本的: (直接用LIS算法就可以解决的)

  • 231 Testing the CATCHER
  • 497 Strategic Defense Initiative
  • 481 What Goes Up

关于LIS算法的基本实现,可参考我之前写的: http://www.sunchangming.com/blog/post/4583.html

下面列些非基本的

10534 - Wavio Sequence

这个问题求Wavio Sequence的最大长度。Wavio Sequence是指,先递增再递减,递增部分的长度和递减部分的长度一样,所以最终这个序列的长度必须是2N+1。

比如 1 2 3 2 1 就是一个Wavio Sequence。

假设给1 2 3 4 5 4 3 2 1 10 这样一个序列,怎么求出它长度最大的Wavio Sequence呢?

假设原数组为A[0...n],可以证明,对于任意的A[i],以它为中心的最大长度的Wavio Sequence就是向左找最长上升序列,向右找最长下降序列,然后拼接起来。最后为了满足2N+1的条件,裁减一下。

我的做法是,做两次LIS,一次从头往尾做,另一次从尾往头做。然后遍历求max。代码如下:

    std::vector<size_t> ret1=lis(nums.begin(),nums.end());
    std::vector<size_t> ret2=lis(nums.rbegin(),nums.rend());
    size_t maxlen(1);
    for(size_t i=0;i!=ret1.size();++i){
      size_t l=ret1[i];
      size_t r=ret2[ret1.size()-i-1];
      if(l==1 || r==1) continue;
      maxlen=std::max(std::min(l,r)*2-1,maxlen);
    }
    std::cout<<maxlen<<"\n";

其中lis算法可以用O(nlgn)的实现,具体我省略掉了,请参见我之前的日志。

10131 - Is Bigger Smarter?

参见 http://www.sunchangming.com/blog/post/4584.html

11368 - Nested Dolls

这个问题是这样:假如我们现在有很多个有序整数对。规定如果a1\<b1 && a2 \<b2,那么(a1,b1) \< (a2,b2)。把满足以上小于关系的都串起来,成为1堆。那么最终至少会形成几堆?

也就是说,求最少个数的LIS,覆盖原有输入。

如果这个问难换成一维的,

1 3 6 10 2 4 8 5

多少个递增子序列,才能覆盖上面这8个数字?

其实很简单,就是求最长的严格递减子序列。

回到原来的问题,这个其实和上面那个10131,elephant的问题一样。对二维数据先按照我定义好的关系排序,然后计算LIS。

排序的时候我让第一个数字递增,第二个数字递减。第二个递减是因为。假设输入为(1,4) (1,5) (2,3)。第二个数字可以排成 4 5 3 或者 5 4 3。但是第二种(递减)会产生长度更大的LDS。

计算LIS的时候我完全不考虑第一个数字。这里是因为,如果输入为(0,1) (0, 2) ,它们第一个数字相同,那么它们必须位于两个不同的LIS序列中。所以我计算出的LDS的值应该为2。也就是说,当计算LDS的时候,如果遇上第一个数字相同但第二个数字递减或相同,则应纳入其中。所以我给LIS定义小于关系的时候,只要求this->second>=r.second。

最终用O(nlgn)的LIS算法求解。所以,最大的难点在于想清楚怎么定义好这两个compare关系。

437 - The Tower of Babylon

这个问题是这样:假如我们有很多种石头,长宽高已知,每种都无限多个,那么如果把它们叠起来,最高能有多高?限制条件是:下面石头的长宽必须小于上面石头的长宽。

例如,如果输入是

10 20 30

那么输出是40。虽然只有一种石头。但是我们把它来回翻个。第一层放(20,30,10) ,第二层放 (10,20,30) ,于是高度等于40。

我首先的做法是,定义一个数据结构

让z代表高度。x,y代表长宽。其中x\<=y。

struct block{
  int x,y,z;
  block(int x1,int y1,int z1):z(z1){
    x=std::min(x1,y1);
    y=std::max(x1,y1);
  }
};

假如我们得到一个10 20 30 这样的输入。那么意味着,我们有三种选择

  1. 让30做为高
  2. 让20做为高
  3. 让10做为高

可以证明,这三种情况,每种最多只能出现一次。反证:假如(x,y,z) 叠在 (y,x,z)之上。那么根据限制条件就得有 x\<y 与 y\<x 同时成立。这不可能。

如果我们在block和block之间定义一个小于关系

bool operator<(const block& l,const block& r) {
  return (l.x> r.x && l.y > r.y);
}

那么就是求能满足这个关系的最长序列。不过这里的长度不是序列的长度,而是把height相加得到的长度。这时候,就能够用LIS算法解决。但是我只会用O(n*n)的方式做,不会O(nlgn)的。

首先,对每一个输入,列出三种情况。

下面对每一行输入,产生三种block

void fillBlocks(std::vector<block>& blocks,const std::string& line){
    char* p=(char*)line.c_str();
    int x=(int)strtol(p,&p,10);
    int y=(int)strtol(p,&p,10);
    int z=(int)strtol(p,&p,10);
    blocks.push_back(block(x,y,z));
    blocks.push_back(block(x,z,y));
    blocks.push_back(block(y,z,x));
}

然后对上述结果sort一下。排序只有一个要求:如果a和b满足前面所定义的小于关系,排序后a必须在b的前面。于是,在这一步我们可以不考虑height,我写了一个简单的排序规则:

struct sortcomp{
  bool operator()(const block& l,const block& r) const{
    if(l.x > r.x) return true;
    if(l.x < r.x) return false;
    if(l.y > r.y) return true;
    if(l.y < r.y) return false;
    return false;
  }
};

强调一下,这个comp函数必须是良好定义的,否则std::sort会崩溃。比如,如果sortcomp(a,b)返回true,那么sortcomp(b,a)必须返回false。

然后就是用O(N*N)的算法复杂度的LIS算法计算最大高度

long lis(const std::vector<block>& a) {
  if (a.empty()) throw std::runtime_error("err");
  if (a.size() == 1) return a[0].z;
  std::vector<long> m(a.size(), 0);
  m[0]=a[0].z;
  size_t top(0);
  for (size_t i = 1; i != a.size(); ++i) {
    m[i]=a[i].z;
    for (size_t j = 0; j < i; ++j) {
      if (a[j] < a[i] && m[j] + a[i].z > m[i]) {
        m[i] = m[j] + a[i].z;
      }
      if (m[i] > m[top]) top = i;
    }
  }

  return m[top];
}

这个问题我找不到O(nlgn)的算法,如果你找到了请告诉我。

11456 - Trainsorting

我的做法是,先求一次LIS。然后求一次LDS。

最终对每一个位置(i=0.....n),计算max(LIS(i)+LDS(i) -1) ,然后输出。

此博客中的热门博文

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

在windows下使用llvm+clang

tensorflow distributed runtime初窥