程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> UVA 10534

UVA 10534

編輯:關於C++

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

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

然後以這個數為中心數的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;
}



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved