DP:Bridging Signals(POJ 1631)

　　　　　　　　　　

　　　　　　　　　　　　　　　　不能交叉的引脚

　　（这一题的难度在于读题）题目大意：有一堆引脚（signals），左边一排，右边一排，左边从上到下，对应着连接右边的引脚（所有的引脚都被接上），现在引脚之间的连线有交叉，我们要桥接这些交叉，而桥接是费事的，现在要你求不交叉引脚的最大数目

　　明白题在说什么以后，是不是感觉豁然开朗？

　　没错，这一题我们只用把左边的引脚从上到下排列（事实上已经排了），然后看右边对应的引脚的上升序最长有多少就可以了

　　昨天我弄了一个Wooden Sticks，这一题也要用到LIS，而且还是直接用LIS，更简单

#include <iostream>
#include <functional>
#include <algorithm>

using namespace std;
typedef int Position;

static int ports[40000];
static int stacks[40000];

void Search(const int);
Position Binary_Search(const int,const int);

int main(void)
{
    int case_sum, ports_sum;
    while (~scanf("%d", &case_sum))
    {
        for (int j = 0; j < case_sum; j++)
        {
            scanf("%d", &ports_sum);
            for (int i = 0; i < ports_sum; i++)
                scanf("%d", &ports[i]);//左边的每一个点对应右边的拿一个点
            Search(ports_sum);
        }
    }
    return 0;
}

Position Binary_Search(const int len,const int item)
{
    int left = 0, right = len, mid;

    while (left <= right && left != len)
    {
        mid = (left + right) / 2;
        if (item < stacks[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}

void Search(const int ports_sum)
{ 
    int pos;
    int length = 1; stacks[0] = ports[0];

    for (int i = 1; i < ports_sum; i++)
    {
        pos = Binary_Search(length,ports[i]);

        stacks[pos] = ports[i];
        if (pos == length)
            length++;
    }
    printf("%d
", length);
}