POJ 1631 Bridging signals

POJ 1631 Bridging signals

題意：給出許多連線，要你刪除一些使得剩下的連線最多且不想交，抽象出來就是最長上升序列問題（LIS）

LIS有兩種經典解法，一種是DPO（N^2)的時間復雜度，還有一種二分O（NlogN）的時間復雜度。

第一種方法：

推薦題目PKOJ2533 ——Longest Ordered Subsequence 裸LIS

#include 
#include
#include
#include
#include
#define N 2222//最長上升子序列，n^2算法
using namespace std;
int dp[N];
int a[N];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
        dp[1]=1;int ans=1;
        for(int i=2;i<=n;i++)
        {
            int m=0;
            for(int j=1;jm&&a[i]>a[j])
                   m=dp[j];
            }
            dp[i]=m+1;
            if(ans

第二種方法：

POJ1631，給的數據40000，直接做的話會超時，所以要用二分來做
http://www.docin.com/p-540470161.html  豆丁上把這種方法講解的很好的一個PPT，看了就懂


#include 
#include
#include
#include
#include
#include
#define N 45000
using namespace std;
int a[N];
int ans[N];//注意，ans數組儲存的不是LIS，而是對應長度LIS的最小末尾
int len;
int binary_search(int i)
{
    int le,ri,mid;
    le=0;ri=len;
    while(le=a[i]) ri=mid;
        else
        le=mid+1;
    }
    return le;
}
int main()
{
    int n;
    int p;
    while(~scanf("%d",&n))
    {
        while(n--)
        {
            scanf("%d",&p);
            for(int i=1;i<=p;i++)
            scanf("%d",&a[i]);
            ans[1]=a[1];
             len=1;
            for(int i=1;i<=p;i++)
            {
                if(ans[len]

有關的題目推薦：POJ 1887  POJ 1609