hdu

最长上升子序列

题目链接
Constructing Roads In JGShining’s Kingdom

Input
Each test case will begin with a line containing an integer n(1 ≤ n ≤ 500,000). Then n lines follow. Each line contains two integers p and r which represents that Poor City p needs to import resources from Rich City r. Process to the end of file.

Output
For each test case, output the result in the form of sample.
You should tell JGShining what’s the maximal number of road(s) can be built.

Sample Input
2
1 2
2 1
3
1 2
2 3
3 1

Sample Output
Case 1:
My king, at most 1 road can be built.

Case 2:
My king, at most 2 roads can be built.

求序列中的最长上升子序列.

首先,LIS(Longest Increasing Subsequence,最长上升子序列)不能用分治合并的方法.例如序列1,3,2,利用分治法将无法得到LIS=2.这是因为在最大子段和的问题中,子段是连续的,而这里的子段是非连续的,当使用分治法处理最长上升子段在中间的情况时,你无法判断究竟是包含了哪些点和跨越了哪些点.

其次, 该问题n太大,不能采用O(n^2)的常规dp方式,而是采用了更加优美的和特殊的二分插入方式,并且该方法的dp规则简直吊炸天.
dp[i]代表了长度为i的子序列末尾的值,当j>i时, dp[j]肯定>dp[i].
将dp[]初始化成最大值,然后i从1到n依次以二分查找的方式插入到dp[]中,时间复杂度O(nlogn).

用到了STL中algorithm的 int *lower_bound(begin, end, value)方法,自带的二分查找最低位置的value, 相似函数还有upper_bound以及验证是否存在的方法binary_search.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<cstdlib>
#define MAX 500010
#define INF 1<<20
#define TEST

using namespace std;

int a[MAX], dp[MAX], n;

/**
* 最长上升子序列
*/
int fun()
{
    //将dp从1到n初始化为INF
    fill(dp+1, dp+n+1, INF);
    //利用二分查找将a[i]插入到dp[]中
    for(int i=1; i <= n; i++)
    {
        int *idx = lower_bound(dp+1, dp+n+1, a[i]);
        *idx = a[i];
    }
    int ans = 0;
    for(int i=1; i<=n; i++)
    {
        if(dp[i] != INF) ans++;
    }
    return ans;
}

int main()
{
#ifdef TEST
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    int ans, rich, poor, tc = 0;
    while(~scanf("%d", &n))
    {
        for(int i = 0; i < n; i++)
        {
            scanf("%d %d", &poor, &rich);
            a[rich] = poor;
        }
        ans = fun();
        if(ans > 1)
        {
            printf("Case %d:\nMy king, at most %d roads can be built.\n\n", ++tc, ans);
        }
        else
        {
            printf("Case %d:\nMy king, at most 1 road can be built.\n\n", ++tc);
        }
    }

#ifdef TEST
    fclose(stdin);
    //fclose(stdout);
#endif // TEST
    return 0;
}