2016级算法第四次上机

1019 ModricWang的序列问题

思路

此题题意非常清晰，给定一个序列，求出最长上升子序列的长度。从数据规模来看，需要\(O(nlogn)\) 的算法。

\(O(nlongn)\) 求最长上升子序列的做法如下：

维护一个数组\(f[]\) ，其中\(f[i]\) 表示当前步骤下长度为i的上升子序列的末尾元素的最小值。

需要注意的是，\(f[i]\) 一定是单调递增的，这个结论十分显然，这里就不做证明了。

使用动态规划思想，对于原序列中的每个元素，都拿去更新一次\(f[]\) 。假设当前元素为\(num[i]\) , \(f[]\) 长度为len(从1开始计数) 更新方法如下：

• 如果\(num[i]>f[len]\) ， 将\(num[i]\) 放到\(f[len]\) 后面

• 否则，找到\(f[len]\) 中第一个比\(num[i]\) 大的位置，并替换它

最后\(f[]\) 的长度就是最长上升子序列的长度。

代码

#include <iostream>
#include <random>

using namespace std;

const int MAXN = 500010;
int nums[MAXN], pool[MAXN];

//用二分查找的方法找到一个位置，使得num>pool[i-1] 并且num<pool[i],并用num代替b[i]
int Search(int num, int low, int high) {
int mid;
while (low <= high) {
        mid = (low + high)/2;
if (num > pool[mid]) low = mid + 1;
else high = mid - 1;
    }
return low;
}

int DP(int n) {
int i, len, pos;
    pool[1] = nums[1];
    len = 1;
for (i = 2; i <= n; i++) {
if (nums[i] > pool[len]) {   //如果a[i]比b[]数组中最大还大直接插入到后面即可
            len = len + 1;
            pool[len] = nums[i];
        } else {    //用二分的方法在b[]数组中找出第一个比a[i]大的位置并且让a[i]替代这个位置
            pos = Search(nums[i], 1, len);
            pool[pos] = nums[i];
        }
    }
return len;
}

int main() {
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
int n;
    cin >> n;
for (int i = 1; i <= n; i++)
        cin >> nums[i];
    cout << DP(n) << "\n";
}