Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

老实写的DP是O(N^2)肯定超时,如果仅仅是需要确定LIS长度有O(NlgN)的算法

Posted by dirtysalt at 2009-07-30 19:02:35 on Problem 3670 and last updated at 2009-07-30 19:05:42
In Reply To:我老老实实的写了个DP Posted by:haolujun at 2008-08-21 23:32:13

网上讲得相当清楚,然后参考一下这个代码.
#define N 30000
int n;
int D[N];//输入数据
int B[N];//B[i]表示长度为i的LIS的最大元素
int
LIS()
{
    int bn = 0;
    for (int i = 0; i < n; i++) {
        int s = 0, e = bn - 1;//这里二分搜索
        while (s <= e) {
            int m = (s + e) / 2;
            if (B[m] <= D[i])
                s = m + 1;
            else
                e = m - 1;
        }
        if (s >= bn)
            B[bn++] = D[i];
        else
            B[s] = D[i];
    }
    return bn;
}

Followed by:

呵呵我的DP 貌似是O(N)的 (0) haolujun 2010-04-08 21:48:02
- 请教O(N)！！！！！ (0) newfolder 2010-04-20 20:00:30

Post your reply here:

Home Page Go Back To top