UVA 10534--Wavio Sequence+二分+DP

UVA 10534--Wavio Sequence+二分+DP

開始的時候一直想不到一個合適的狀態轉移方程；

後面想到可以分別求以中間那個數為終點和起點的最長上升子序列的長度，

然後以這個數為中心數的Wavio Sequence的長度就是其中短的那個值*2-1的值；

然後我們取所有數Wavio Sequence的最大長度作為答案。

這個題目卡了n^2的求最長上升子序列的算法，必須用nlgn算法才能過。

代碼如下：

#include
#include
#include
#include
using namespace std;

int a[10010],n;
int d1[10010],d2[10010];
int d[10010];

int lower_bound(int* A,int x,int y,int v)
{
    int m;
    while(x=v)
            y=m;
        else
            x=m+1;
    }
    return x;
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
         for(int i=1;i<=n;i++)
             scanf("%d",&a[i]);
         for(int i=1;i<=n;i++)
            d1[i]=1,d2[i]=1;
         int len=1;
         d[1]=a[1];
         for(int i=2;i<=n;i++)
         {
             if(a[i]>d[len])
             {
                 d[++len]=a[i];
                 d1[i]=len;
             }
             else
             {
                 int t=lower_bound(d,1,len,a[i]);
                 d[t]=a[i];
                 d1[i]=t;
             }
         }
         len=1;
         d[1]=a[n];
         for(int i=n-1;i>=1;i--)
         {
             if(a[i]>d[len])
             {
                 len++;
                 d[len]=a[i];
                 d2[i]=len;
             }
             else
             {
                 int t=lower_bound(d,1,len,a[i]);
                 d[t]=a[i];
                 d2[i]=t;
             }
         }
        int ans=0;
        for(int i=1;i<=n;i++)
            ans=max(ans,min(d1[i],d2[i])*2-1);
        printf("%d\n",ans);
    }
  return 0;
}