這道題的意思是讓我們求一個上升子序列 　+　一個下降字序列，且兩邊的長度是相等的，由于用正常的　O(n2)　算法會　TLE　，所以這里我們采用二分法求最長上升子序列，這里需要利用兩個棧來儲存“相當于”最長上升子序列的串（我利用一個棧通過再次初始化棧頂ｔｏｐ來第二次使用），在此同時開兩個數組ｆ１［ｉ］，ｆ２［ｉ］，分別表示前i個元素的最長字串長度，最后比較同一個位置時（注意ｆ１，ｆ２一個正一個反）兩個數組值的大小，取小的一個（因為要求兩邊長度相等）賦值給新開的數組ｆｌａｇ［］（我用ｎｕｍ不斷刷新），最后遍歷數組，找出其最大的就可以了。

這里說一下二分法求最長上升子序列：復雜度為O(n×logn)：

它是通過一個棧來實現的，我們遍歷一個母串，如果當前值大于棧頂元素的值，我們將其壓入棧，而當前位置　i　的最長上升子序列的長度就是棧頂指針的值（或＋１），如果當前值等于棧頂元素的值，不壓入棧，同樣當前位置　i　的最長上升子序列的值就是棧頂指針的值（或＋１），如果當前值小于棧頂元素的值，不壓入棧，但是我們要用二分法找出恰好不小于當前值的那個位置，這個位置我們這里定義為ｘ，并將ｘ位置的值替換為當前值，而當前位置　i　的最長上升子序列的長度就是ｘ這個指針的值（或＋１）；

為什么這樣是成立的呢：別人的證明：

實際上就是運用了貪心的思想，每次進行替換操作后增強了后續最長上升子序列的“長度增長的潛力”，后續得到的解一定不會比不替換更優。

? ? 簡單證明一下其正確性。我們用a[i]替換掉了S[mid]，對后續某一元素a[j]來講，可能會認為此時a[j]前的元素標號并不是嚴格升序了，這會不會有問題呢？實際是不會有問題的。我們不妨設a[j]左邊的元素依次為A1、A2、……，這樣A1我們必然可以不動，因為此前A1已經更新至最新了，標號必然是所有曾在這個位置的元素中的標號最大的一個，那么對于A2呢，我們不妨想想現在的A1剛進入這個棧的時候吧，那個時候的A2必然也在那個時候之前更新到當時的最新了吧，并且A1左邊的元素的個數從那個時刻起也沒有變過吧？現在這個問題就可以不斷遞歸下去了，我們按這種方式一定可以找到一個序號嚴格遞增的序列，即使這個序列并不是在a[j]入棧時我們所看到的序列，但這又有什么關系呢，反正結果對就是了。

? ? 再簡單說明一下其最優性。既然前面已經證明了其正確性，那么按前面的方法至少可以得到一個長度可觀的最長上升子序列，但究竟其是否是最長的呢？按上面算法的思路，如果想要得到的長度更長的話，那么只有一個措施，就是將原來的替換操作變成插入操作，要不然是沒辦法增加長度的。然而如果將替換操作變成插入操作，我們還能保證一定可以得到一個標號嚴格升序的上升子序列嗎？顯然不能。比如一次插入操作在S[k]和S[k+1]之間，我們插入了一個a[i]，但是如果此時有a[j]>S[k+1]，那么a[j]的左邊是沒辦法構造出一個長度為k+2的標號嚴格升序的上升子序列的。既然第一次插入操作都會有錯，那肯定就不用考慮后續再有插入操作了。

代碼如下：

#include<stdio.h>
#define MAXN 10010
int a[MAXN], f[MAXN], f1[MAXN], f2[MAXN];
int n,num;
int up_bd(int *f, int t, int v)
{
int m;
int first = 0;
while(first < t)
{
m = first + (t - first)/2;
if(f[m] < v) first = m + 1;
else t = m;
}
f[first] = v;
return first;
}
void solve()
{
int top;
top = 0;
f[0] = a[0];
f1[0] = 1;
int x,y;
for(int i = 1; i < n; i ++)
{
if(a[i] > f[top]) {f[++top] = a[i];x = top + 1;}
else if(a[i] == f[top]) {f[top] = a[i];x = top + 1;}
else if(a[i] < f[top]) x = up_bd(f,top,a[i])+1;
f1[i] = x;
}
top = 0;
f[0] = a[n-1];
f2[0] = 1;
for(int i = n-2; i >= 0; i --)
{
if(a[i] > f[top]) {f[++top] = a[i];y = top + 1;}
else if(a[i] == f[top]) {f[top] = a[i];y = top + 1;}
else if(a[i] < f[top]) y = up_bd(f,top,a[i])+1;
f2[n-1-i] = y;
}
num = 0;
int min = 0;
for(int i = 0; i < n; i ++)
{
if(f1[i] > f2[n-i-1]) min = f2[n-i-1];
else min = f1[i];
if(min > num) num = min;
}
printf("%d\n",2*num - 1);
}
void input()
{
while(scanf("%d",&n) == 1)
{
for(int i = 0; i < n; i ++)
scanf("%d",&a[i]);
solve();
}
}
int main()
{
input();
return 0;
}

轉載于:https://www.cnblogs.com/yuzhaoxin/archive/2012/03/31/2427740.html

總結

以上是生活随笔為你收集整理的UVA 10534 - Wavio Sequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。