[TIOJ 1441] 萬里長城

作法：

因為題目要的是高低相間，所以可以想到要維護的東西是「以"低"結尾的子序列」和「以"高"結尾的子序列」們，用和LIS一樣的想法，那麼要維護的陣列就是「長度為 i 的以"低"結尾的子序列」的最低高度，以"高"結尾則反過來。但在更新DP陣列時，他不像LIS的更新的時候可以直接把新的值覆蓋上去，因為他是拿另一個陣列來更新自己的陣列，所以我的解決方法是直接從右邊一路更新到左邊，一有比較差的就 break ，但這樣就不知道複雜度怎麼估了......還好他沒有TLE掉@@

code :

#include<bits/stdc++.h>
#define INF 2147483647
using namespace std;
const int maxn=1000000+10 ;
 
int dp[2][maxn] ; /// 0 : high  , 1 : low
int num0,num1 ;
main()
{
    int n ; scanf("%d",&n) ;
    dp[1][0]=0 ; dp[0][0]=INF ;
    num0=num1=0 ;
    for(int i=1;i<=n;i++)
    {
        int x ; scanf("%d",&x) ;
        int id0=lower_bound(dp[0],dp[0]+num0+1,x,greater<int>() )-dp[0] ;
        int id1=lower_bound(dp[1],dp[1]+num1+1,x)-dp[1] ;
 
        for(int j=id1;j>=0&&( j>num0||dp[0][j]<x );j--) dp[0][j]=x ;
        for(int j=id0;j>=0&&( j>num1||dp[1][j]>x );j--) dp[1][j]=x ;
        if(id1>num0) num0=id1 ;
        if(id0>num1) num1=id0 ;
    }
    printf("%d\n",num0%2 ? num0 : num0-1) ;
}