UVA10534 Wavio Sequence - c++编程基础

题意：给你一串序列，让你序列中找出类似这样的 1 2 3 4 5 4 3 2 1 的最大长度的子串，子串特性：1长度可以写成2*n+1，其中前n+1的序列是严格上升的，后n+1个是严格递减的；

一开始我的思路是这样的：第一遍先dp一遍，找出所有的递增序列，并且记录上升序列最后一个元素的位置，第二遍从这些上升序列的最后一个元素的位置开始寻找，若能找到一个长度与上升相等的下降序列就停止可以输出了，而且要从最长的开始找，这个想法个人认为是没有什么问题的，但是写起来比较难处理，很难表达，后来又重新换了个思路：

先顺着dp一遍，再逆着dp一遍，都dp上升序列，第二遍dp的是它的逆序，而且对于符合性质的子串他们的 dp1[i] == dp2[n - i + 1],这个稍微推一下就知道了，这样就比较好处理了，直接正反一次 nlong方法即可，但是原先的版子有问题，后来换了个版子过了，

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                //#define ll long long #define ll __int64 #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp1[100000 + 5]; int num[10000 + 5]; int dp2[100000 + 5]; int tmp[10000 + 5]; int n; void clear() { memset(dp1,0,sizeof(dp1)); memset(num,0,sizeof(num)); memset(dp2,0,sizeof(dp2)); memset(tmp,0,sizeof(tmp)); } void LIS(int *dp,int *a) { // nlogn的LIS,n^2会超时的 int Stack[10000 + 5]; Stack[0] = -1; int top = 0; for(int i=1;i<=n;i++) { int left = 1; int right = top; int pos = -1; while(left <= right) { int mid = (left + right)/2; if(Stack[mid] < a[i]) left = mid + 1; else right = mid - 1; } Stack[left] = a[i]; dp[i] = 1; if(a[i] > Stack[top]) { Stack[++top] = a[i]; dp[i] = top; } } } int main() { while(scanf("%d",&n) == 1 ) { clear(); for(int i=1;i<=n;i++) { scanf("%d",&num[i]); tmp[n - i + 1] = num[i];//tmp相当于num的倒序 } LIS(dp1,num); LIS(dp2,tmp); int ans = -1,temp = 0; for(int i=1;i<=n;i++) { temp = min(dp1[i],dp2[n - i + 1]) * 2 - 1;//记得找小的那个 ans = max(temp,ans); } printf("%d\n",ans); } return EXIT_SUCCESS; }