http://poj.org/problem?id=1065

首先双关键字排序。
讨论pair的second值,有如下结论:
某序列的最少上升子序列数就是该序列的最长下降子序列的长度。
如序列2 1 5 3 4,其至少可分成2个上升子序列{2,5}和{1,3,4},但其最长下降子序列的长度也是2。

/*16ms,248KB*/

const int mx = 5005;

p2 p[mx];
int dp[mx];

int get_lis(int n) /// O(nlog n)
{
    mem(dp, 0x3f);
    int i;
    For(i, n) dp[Lowpos(dp, n, p[i].second)] = p[i].second;
    return Lowpos(dp, n, inf);
}

int main()
{
    int t, n, a, b, i;
    SI(t);
    while (t--)
    {
        SI(n);
        For(i, n) SII(a, b), p[i] = MP(a, b);
        sort(p, p + n, greater<p2>());
        PI(get_lis(n));
    }
    return 0;
}

Comments

comments powered by Disqus