主题链接：

pid=1025">http://acm.acmcoder.com/showproblem.php?pid=1025

题意：本求最长公共子序列。但数据太多。

转化为求最长不下降子序列。太NB了。复杂度n*log(n).

解法：dp+二分

代码：

#include <stdio.h>

#include <string.h>

#include <vector>

#include <string>

#include <algorithm>

#include <iostream>

#include <iterator>

#include <fstream>

#include <set>

#include <map>

#include <math.h>

using namespace std;

const int MAXN = 500010;

int n, pos;

int a[MAXN];

int dp[MAXN];

int h, k;

int search(int num,int low,int high)

{

    int mid;

    while (low <= high)

    {

        mid = (low + high) / 2;

        if (num >= dp[mid]) low = mid + 1;

        else high = mid - 1;

    }

    return low;

}

int main()

{

    int cases = 1;

    while (~scanf("%d", &n))

    {

        for (int i = 1; i <= n; i++)

        {

            scanf("%d%d", &h, &k);

            a[h] = k;

        }

        memset(dp, 0, sizeof(dp));

        dp[0] = -1; dp[1] = a[1];

        int len = 1;

        //  n*log(n) 求解

        for (int i = 2; i <= n; i++)

        {

            if (a[i] >= dp[len])

            {

                len = len + 1;

                dp[len] = a[i];

            }

            else

            {

                pos = search(a[i],1,len);

                dp[pos] = a[i];

            }

        }

        printf("Case %d:\n",cases++);

        if (len == 1)

            printf("My king, at most %d road can be built.\n\n",len);

        else

            printf("My king, at most %d roads can be built.\n\n",len);

    }

    return 0;

}

版权声明：转载请注明出处。