題意：給定一個序列，求一個最長的序列，使得他的前半部分是遞增的，而后半部分是遞減的，且兩部分的長度一樣。

思路：經典的LIS問題，和openjudge登山問題一樣，前后各掃一遍，找到前置和倒置的LIS，然后遍歷一遍找到最大的ans即可

code：

#include <bits/stdc++.h> using namespace std;const int N=10005; const int INF=0x3f3f3f3f;int v[N],l[N],r[N],f[N]; int main() {int n,ans;while (~scanf("%d",&n)){for (int i=1;i<=n;i++) scanf("%d",&v[i]),f[i]=INF;f[0]=0;for (int i=1;i<=n;i++){int p=lower_bound(f,f+1+n,v[i])-f;l[i]=p;f[p]=v[i];}for (int i=1;i<=n;i++) f[i]=INF;f[0]=0;for (int i=n;i>=1;i--){int p=lower_bound(f,f+1+n,v[i])-f;r[i]=p;f[p]=v[i];}ans=0;for (int i=1;i<=n;i++) ans=max(ans,min(l[i],r[i]));printf("%d\n",ans*2-1);} }

總結

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

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