poj1631

Description

'Oh no, they've done it again', cries the chief designer at the Waferland chip factory. Once more the routing designers have screwed up completely, making the signals on the chip connecting the ports of two functional blocks cross each other all over the place. At this late stage of the process, it is too expensive to redo the routing. Instead, the engineers have to bridge the signals, using the third dimension, so that no two signals cross. However, bridging is a complicated operation, and thus it is desirable to bridge as few signals as possible. The call for a computer program that finds the maximum number of signals which may be connected on the silicon surface without crossing each other, is imminent. Bearing in mind that there may be thousands of signal ports at the boundary of a functional block, the problem asks quite a lot of the programmer. Are you up to the task?

A typical situation is schematically depicted in figure 1. The ports of the two functional blocks are numbered from 1 to p, from top to bottom. The signal mapping is described by a permutation of the numbers 1 to p in the form of a list of p unique numbers in the range 1 to p, in which the i:th number specifies which port on the right side should be connected to the i:th port on the left side.Two signals cross if and only if the straight lines connecting the two ports of each pair do.

Input

Output

Sample Input

4
6
4
2
6
3
1
5
10
2
3
4
5
6
7
8
9
10
1
8
8
7
6
5
4
3
2
1
9
5
8
9
2
3
1
7
4
6

Sample Output

3
9
1
4

解答：

#include <iostream>

using namespace std;

int psearch(const int f[],int size,const int a)
{
    int l = 0,r = size-1;
    while(l<=r)
    {
        int mid = (l+r)/2;
        if (a>=f[mid-1]&&a<f[mid]) return mid;
        else if (a<f[mid]) r = mid-1;
        else l = mid+1;
    }
}
int LIS(const int aa[],const int bb)
{
    int f[40000];
    int jj,size=1;
    f[0] = aa[0];
    int i;
    for (i = 1;i<bb;i++)
    {
        if (aa[i] < f[0]) jj = 0;
        if (aa[i]>=f[size-1])  jj =size++;
        else jj = psearch(f, size, aa[i]);
        f[jj] = aa[i];
    }
    return size;
}
int main()
{
    int n;
    while(cin>>n)
    {
        int a;
        int duilie[40000];
        for (int i = 0;i<n;i++)
        {
            cin>>a;
            for (int j = 0;j<a;j++)
            {
                cin>>duilie[j];
            }
            cout<<LIS(duilie,a)<<endl;
        }
    }
    return 0;
}

解答思想，见下面这个实例：

在军训的第一天，小班同学还没有安排好队次，大家混着站成了一排，因而有的较矮的同学站在了较高同学中间。现在班长希望指定部分同学向前一步走，出来的这些同学正好是按照由矮到高，不递减的次序排列的，那么，他最多能够指定多少同学向前走呢？
以下面的例子为例：
假定同学身高为（单位很特殊，所以不要纠结单位的问题）：
5 7 8 2 3 9 5 8 7 8
那么最多指定同学的策略是：
5 7 8 X X X X 8 X 8
或者：
X X X 2 3 X 5 8 X 8
想想怎么找出这个序列。
 
提示：
最常用的方法是O(n^2)的，使用递推的方式实现。有特别的叫最长递增序列的算法，可以减少复杂度。
 
答案：
这是经典的Longest Increasing Sequence(LIS)算法。传统做法为简单DP，时间复杂度为O(n^2)，其中n为序列长度。LIS算法可以使时间复杂度达到O(nlogn)，能够解决较大的数据规模。
传统DP思想如下：
假设原数组为a[]。定义dp[k]表示以第k个元素作为序列最后一个元素时，最长的公共子序列长度为dp[k]。显然，dp[1] = 1。如果我们知道了dp[1]…dp[k]的值，那么，dp[k+1]的值为：
对于所有的i<=k并且a[k+1] > a[i]，dp[k+1] = max{dp[i] +1}。
通过上述方法，从第1位开始向后扫一遍，即可得到结果，时间复杂度为O(n^2)。
那么LIS算法是怎么实现的呢。
LIS算法：
定义一个数组c[]，c[p]表示在当前检测的情况下，最长长度为p时，序列结尾的最小值。
假设c中元素有m个，表示LIS长度为m。其中c[1]为最长长度为1时，结尾元素的最小值，c[m]为最长长度为m时，结尾元素的最小值，那么，在扫描a中第k个元素时，有如下两类操作：
<!--[if !supportLists]-->1、  如果a[k] > c[m]，表示当前元素可以放在前面已有的长度为m的序列后，这样就形成了长度为m+1的递增序列。我们将a[k]插入到c[m]后，此时c中元素有m+1个。
<!--[if !supportLists]-->2、  如果a[k] < c[m]，那么找出c中的元素c[l]，使得c[l] < a[k] 并且 c[l+1] > a[k]。这表示a[k]能接在序列长度为l的元素后形成长度为l+1的序列，并且该序列的最后一个元素比原c[l+1]小，通过这种方式，我们维护了c数组。
以题目数据为例
 
 

由上表可以看出算法执行过程。

在这操作中，我们只需要更新，不需要移动，因此，我们可以使用二分法定位更新位置，由此可以将每次更新的时间降到O(logn)，所以得解。

在此附上参考代码：

int a[N], f[N], d[N]; // d[i]用于记录a[0...i]的最大长度

  int bsearch(const int *f, int size, const int &a) {

    int l = 0, r = size - 1;

    while (l <= r) {

        int mid = (l + r) / 2;

        if (a > f[mid - 1] && a <= f[mid]) return mid; // >&&<= 换为: >= && <

        else if (a < f[mid]) r = mid - 1;

        else l = mid + 1;

    }

  }

  int LIS(const int *a, const int &n) {

    int i, j, size = 1;

    f[0] = a[0];

    d[0] = 1;

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

        if (a[i] <= f[0]) j = 0; // <= 换为: <

        else if (a[i] > f[size - 1]) j = size++; // > 换为: >=

        else j = bsearch(f, size, a[i]);

        f[j] = a[i];

        d[i] = j + 1;

    }

    return size;

  }

  int main(void) {

    int i, n;

    while (scanf("%d", &n) != EOF) {

        for (i = 0; i < n; ++i) scanf("%d", &a[i]);

        printf("%d/n", LIS(a, n)); // 求最大递增/上升子序列(如果为最大非降子序列,只需把上面的注释部分给与替换)

    }

    return 0;

  }