找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2009|回复: 9
收起左侧

[讨论] Make Sequence in Ascending Order - 搬运&心得理解

[复制链接]

30

主题

5

精华

283

积分

高级会员

Rank: 3Rank: 3

积分
283
发表于 2-26-2015 03:36 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
这是一道Meetqun OJ的题目,SPOJ上也见过。标记是Hard。于是我就尝试了一下。题目就不传送了,直接点Online Judge的problem40.
大意是给一个array,要求replace其中的一些数字,使得replace过后的array是严格递增的。求replace可能的最小元素个数。
第一眼就很确定肯定是用LIS来解决,一看数据范围肯定是那种binary search的O(nlogn)的LIS。

我记得在国内一个OJ上见过一题:给定一个array,要求删除一些数字,使得删除过后的array是严格递增的。求replace可能的最小元素个数。
这道题和Meetqun OJ上的题目就差了一个操作。可如果操作是删除的话那就简单很多。因为答案就是len(arr) - len(LIS(arr))
原理很简单,求LIS和最少删除操作,本身就是互补行为。 所以一个最长,另一个就最少咯


但是replace是有要求的,比如一个简单的例子:
arr = [1 2 2 3 4] LIS = [1 2 3 4]
可是这能work么?不能
因为你如果把1 2 3 4留下了不管你怎么替换剩下的那个2都无法得到一个严格递增序列。
既限制了元素的单调性,又限制了元素大小和下标之间的关系。也就是这一题的难点。更是这一题无法直接单纯套用LIS求出来的原因。

纠结了很久,然后还是可耻了上了CF瞄到一个解答。那个解答TLE,我在它的基础上优化了一下。得到如下code
  1.   private int bs(int [] dp, int cnt, int idx, int[] arr) {
  2.     int key = arr[idx] - idx;
  3.     if(key < 1) {
  4.       return 0;
  5.     }
  6.     int beg = 0, end = cnt - 1;
  7.     while(beg <= end) {
  8.       int mid = (beg + end) >>> 1;
  9.       if(mid == 0 && key < dp[mid] || mid > 0 && dp[mid-1] <= key && dp[mid] > key) {
  10.         dp[mid] = key;
  11.         return 0;
  12.       } else if(dp[mid] > key) {
  13.         end = mid - 1;
  14.       } else {
  15.         beg = mid + 1;
  16.       }
  17.     }

  18.     dp[cnt] = key;
  19.     return 1;
  20.   }

  21.   public int makeSequence(int [] a) {
  22.     int len = a.length;
  23.     int [] dp = new int [len];
  24.     int cnt = 0;

  25.     for(int i = 0; i < len; i ++) {
  26.       cnt += bs(dp, cnt, i, a);
  27.     }

  28.     return len - cnt;
  29.   }
复制代码
code写的有点乱。

诀窍就在于这题目对LIS有了新的定义,我们暂且叫他Special-LIS。一般来说求LIS我们只要求元素单调性:
即在LIS中,array[y] > array[x] (y > x)

可这一题Special-LIS要满足如下条件:
若在array里存在两个元素array[x], array[y]且x < y
那么这两个元素必须满足: array[y] - array[x] >= y - x它们才有可能同时存在于Special-LIS里面

理由很简单,如果array[y] - array[x] < y - x那么它们之间的元素array(x...y)不管怎么替换都不可能使得array[x...y]严格递增。
生动一点的例子 arr = [1 2 9 3], 那么2和3就不可能同时存在于Special-LIS中

换句话说Special-LIS里所有的元素都满足 array[y] - array[x] >= y - x


这也是这题的解法所在了,我们对这个关键的式子进行移项,得到 array[y] - y >= array[x] - x
我们把array【i】 - i看做一个整体,那么我们如果把array的每一项减去它的index,得到Special-array,再对Special-array求普通的LIS。就是我们想要的答案了。

edge case就是bs函数里面先会考虑key和1之间的大小关系,如果key小于1那么直接返回。原因是如果array【i】 - i < 1那就根本不能考虑这个数存在于Special-LIS里面的可能性,因为如果他存在Speical-LIS中,那么他之前的数无论怎么replace都不可能构成一个严格递增序列。

总之,这题最关键的地方,就是想清楚不等书关系,然后向LIS问题reduce。




47

主题

2

精华

379

积分

高级会员

Rank: 3Rank: 3

积分
379
发表于 3-1-2015 10:35 PM | 显示全部楼层
这么好的贴,居然没人顶。。。
回复 支持 反对

使用道具 举报

47

主题

2

精华

379

积分

高级会员

Rank: 3Rank: 3

积分
379
发表于 3-2-2015 05:42 AM | 显示全部楼层
CF是啥,求大牛指点
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表