学步园

POJ  3903 Stock Exchange :

       此题也是简单的最长上升子序列问题，但由于数列长度n较大（n <= 100000），所以普通的O(n^2)是会超时的，所以要用O(nlogn)算法。加输入输出优化后直接进status前三名，哈哈

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std ;
const int MAXN = 1e5 + 5 ;
int s[MAXN] ;
int dp[MAXN] ;
int n ;
int stap[MAXN] ;
int top ;
inline void RD(int &a)  
{
    a = 0 ;
    char t ;
    do
    {
        t = getchar() ;
    }while ( t < '0' || t > '9') ;
    a = t - '0' ;
    while ((t = getchar()) >= '0' && t <= '9')
    {
        a = a * 10 + t - '0' ;
    }
}
inline void OT(int a)
{
    if(a >= 10)
    {
        OT(a / 10) ;
    }
    putchar(a % 10 + '0') ;
}
void init()
{
    int i , j ;
    for(i = 1 ; i <= n ; i ++)
    {
        //scanf("%d" , &s[i]) ;
        RD(s[i]) ;
    }
}
void solve()  // O(n^2) 算法
{
    int i , j ;
    dp[1] = 1 ;
    for(i = 2 ; i <= n ; i ++)
    {
        dp[i] = 1 ;
        for(j = 1 ; j < i ; j ++)
        {
            if(s[i] > s[j] && dp[i] < dp[j] + 1)
            {
                dp[i] = dp[j] + 1 ;
            }
        }
    }
    int MAX = -1 ;
    for(i = 1 ; i <= n ; i ++)
    {
        if(MAX < dp[i])
        MAX = dp[i] ;
    }
    printf("%d\n" , MAX) ;
}

void solve2()  // O(n log n) 算法
{
    top = 0 ;
    stap[++ top] = s[1] ;
    int i ;
    for(i = 2 ; i <= n ; i ++)
    {
        if(s[i] > stap[top])
        {
            stap[++ top] = s[i] ;
        }
        else if(s[i] < stap[top])
        {
            int left , right , mid ;
            left = 1 ;
            right = top ;
            while (left < right)
            {
                mid = (left + right) / 2 ;
                if(stap[mid] < s[i])
                {
                    left = mid + 1 ;
                }
                else if(stap[mid] == s[i])
                {
                    break ;
                }
                else
                {
                    right = mid ;  // 注意不是 mid - 1  ！！
                }
            }
            mid = (left + right) / 2 ;
            stap[mid] = s[i] ;
        }
    }
    OT(top) ;
    puts("") ;
}
int main()
{
    while (scanf("%d" , &n) != EOF)
    {
        init() ;
        //solve() ;
        solve2() ;
    }
    return 0 ;
}

POJ 1631 Bridging signals：

方法同上，只不过输入发生了点变化。

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std ;
const int MAXN = 1e5 + 5 ;
int s[MAXN] ;
int dp[MAXN] ;
int n ;
int stap[MAXN] ;
int top ;
inline void RD(int &a)
{
    a = 0 ;
    char t ;
    do
    {
        t = getchar() ;
    }while ( t < '0' || t > '9') ;
    a = t - '0' ;
    while ((t = getchar()) >= '0' && t <= '9')
    {
        a = a * 10 + t - '0' ;
    }
}
inline void OT(int a)
{
    if(a >= 10)
    {
        OT(a / 10) ;
    }
    putchar(a % 10 + '0') ;
}
void init()
{
    RD(n) ;
    int i , j ;
    for(i = 1 ; i <= n ; i ++)
    {
        RD(s[i]) ;
    }
}
void solve2()  // O(n log n) 算法
{
    top = 0 ;
    stap[++ top] = s[1] ;
    int i ;
    for(i = 2 ; i <= n ; i ++)
    {
        if(s[i] > stap[top])
        {
            stap[++ top] = s[i] ;
        }
        else if(s[i] < stap[top])
        {
            int left , right , mid ;
            left = 1 ;
            right = top ;
            while (left < right)
            {
                mid = (left + right) / 2 ;
                if(stap[mid] < s[i])
                {
                    left = mid + 1 ;
                }
                else if(stap[mid] == s[i])
                {
                    break ;
                }
                else
                {
                    right = mid ;  // 注意不是 mid - 1  ！！
                }
            }
            mid = (left + right) / 2 ;
            stap[mid] = s[i] ;
        }
    }
    OT(top) ;
    puts("") ;
}
int main()
{
    int T ;
    scanf("%d" , &T) ;
    while (T --)
    {
        init() ;
        solve2() ;
    }
    return 0 ;
}