欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 1631 - Bridging signals ( LIS )

程序员文章站 2022-03-16 17:33:40
...

题意

POJ 1631 - Bridging signals ( LIS )
有p条线路,它们有可能相交。现在让你去掉一些线路,使得剩下的线不相交且线最多 ( p < 40000 )

思路

为使得连线不相交, 必须选择一个上升的连接序列, 而求剩下的线不相交且最多就是求LIS ( 最长上升子序列 )
由于p最大达40000, 1000 ms 肯定不能用复杂度为O(n*n)的朴素动态规划,会超时。这时考虑用O(nlogn)二分+贪心

建一个dp数组,dp[i]表示长度为i的LIS结尾元素的最小值。贪心策略:对于一个上升子序列,显然其结尾元素越小,越有利于在后面接其他的元素,也就越可能变得更长。因此,我们只需要维护dp数组,对于每一个a[i],如果a[i] > len[当前最长的LIS长度],就把a[i]接到当前最长的LIS后面,即dp[++当前最长的LIS长度]=a[i]。


关于维护dp数组 :
对于每一个a[i],如果a[i]能接到LIS后面,就接上去;否则,就用a[i]取更新dp数组。具体方法是,在dp数组中找到第一个大于等于a[i]的元素dp[j],用a[i]去更新dp[j]。如果从头到尾扫一遍dp数组的话,时间复杂度仍是O(n^2)。我们注意到dp数组内部一定是单调不降的,所有我们可以二分dp数组,找出第一个大于等于a[i]的元素。二分一次dp数组的时间复杂度的O(logn),所以总的时间复杂度是O(nlogn)。

目前为止看到过的最易理解的LIS – O(nlogn)算法分析:
最长上升子序列(LIS)长度的O(nlogn)算法

AC代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;
const int maxn = 40000+5;
const int INF = 0x3f3f3f3f;
int dp[maxn], a[maxn];

int main()
{
    int T, n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for( int i = 0; i < n; i++ )
            scanf("%d",&a[i]);
        int len = 1;
        for( int i = 0; i < n; i++ ){
            int p = lower_bound(dp, dp+len, a[i]) - dp;
            dp[p] = a[i];
            if( p == len ) len++;
        }
        printf("%d\n",len-1);
    }
    return 0;
}