[Code] LIS cải tiến C++

// tim kiem nhi phan: tìm nhỏ nhất >= k
int tim(int k) {
    int d,c,g,kq;
    d=0,c=s.size()-1;
    kq=c+1;
    while (d<=c) {
        g=(d+c)/2;
        if (k<=a[s[g]]) {
            kq=g;
            c=g-1;
        }else d=g+1;
    }
    return kq;
}

main() {
//...
    s. push_back(0);
    s. push_back(1);
    d[1]=1;
    for (i=2;i<=n;i++) {
        d[i]=tim(a[i]);
        if (d[i]==s.size()) s. push_back(i);
        else if (a[i]<a[s[d[i]]]) s[d[i]]=i;
    }
//...
}

Đăng bởi Unknown lúc lúc tháng 11 12, 2014 0 bình luận