CF 446A DZY Loves Sequences

题目链接~~>

做题感悟：原本以为A题很简单想水过，水了老半天也没最后wa了二次终于AC了。

解题思路：

                本人：先遍历一下用dp0[ i ] 记录以 i 为终点连续的个数。再遍历一遍用dp1[ i ] 记录以 i 为结尾的改变一个的连续个数。改变一个可以分几种情况：（1）g[ i-1 ]可以改变为 g[ i-2 ] 和g[ i ] 的中间数 - > dp [ i ] = dp [ i-2 ] + 2 ; (2)  g [ i -1 ] 小于 g [ i ] 更新 dp1[ i ] = max ( dp1[ i ], dp[ i-1 ] + 1 , dp1[ i -1 ] + 1 ) ; (3) 否则 只改变 g[ i - 1 ]  , dp1[ i ] = 2 ;

更新ans是要注意！。 

            优思路：用L [ i ] 记录以 i 为终点的最大连续个数 ， R[ i ] 记录以 i 为起点的最大连续个数。（1）如果g [ i ] - g [ i-2 ] >= 2 则  ans = max { L[ i-2 ] + R [ i ] +1, ans } .(2 ) 否则      ans = max { ans , L[ i ] +1 , R [ i ] +1 }

代码（优代码）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int INF = 99999999 ;
     
    
   

    

     

    
    

     

      const double esp = 0.0000001 ;
     
    
   

    

     

    
    

     

      const int MX = 100000 + 10 ;
     
    
   

    

     

    
    

     

      int ans,n ;
     
    
   

    

     

    
    

     

      int g[MX],L[MX],R[MX] ;
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 while(~scanf("%d",&n))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 memset(L,0,sizeof(L)) ;
     
    
   

    

     

    
    

     
 memset(R,0,sizeof(R)) ;
     
    
   

    

     

    
    

     

       L[0]=1 ;
     
    
   

    

     

    
    

     

       n > 1 ? ans =2 : ans =1 ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d",&g[i]) ;
     
    
   

    

     

    
    

     

       i&&g[i-1]<g[i] ? L[i]=L[i-1]+1 : L[i] = 1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       R[n-1]=1 ;
     
    
   

    

     

    
    

     
 for(int i=n-1 ;i>=0 ;i--)
     
    
   

    

     

    
    

     

       g[i]<g[i+1] ? R[i] = R[i+1]+1 : R[i] = 1 ;
     
    
   

    

     

    
    

     

       ans = max(R[1]+1,ans) ;
     
    
   

    

     

    
    

     
 for(int i=2 ; i<n ;i++)
     
    
   

    

     

    
    

     

       g[i]-g[i-2]>=2 ? ans = max(ans,L[i-2]+R[i]+1) : ans = max(ans,max(L[i-1]+1,R[i]+1)) ;
     
    
   

    

     

    
    

     
 cout<<ans<<endl ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

代码（本人）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int INF = 99999999 ;
     
    
   

    

     

    
    

     

      const double esp = 0.0000001 ;
     
    
   

    

     

    
    

     

      const int MX = 100000 + 10 ;
     
    
   

    

     

    
    

     

      int ans,n ;
     
    
   

    

     

    
    

     

      int dp1[MX],g[MX],dp[MX] ;
     
    
   

    

     

    
    

     

      void init()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 memset(dp,0,sizeof(dp)) ;
     
    
   

    

     

    
    

     

       dp[0]=1 ;
     
    
   

    

     

    
    

     
 for(int i=1 ;i<n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(g[i]>g[i-1])
     
    
   

    

     

    
    

     

       dp[i]=dp[i-1]+1 ;
     
    
   

    

     

    
    

     
 else dp[i]=1 ;
     
    
   

    

     

    
    

     

       ans = max(dp[i],ans) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void solve()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 memset(dp1,0,sizeof(dp1)) ;
     
    
   

    

     

    
    

     

       dp1[0]=1 ;
     
    
   

    

     

    
    

     

       ans=1 ;
     
    
   

    

     

    
    

     
 if(n>=2)
     
    
   

    

     

    
    

     

       dp1[1]=2,ans =2 ;
     
    
   

    

     

    
    

     
 for(int i=2 ;i<n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(g[i]-g[i-2]>=2&&(g[i-1]==g[i-2]||g[i-1]==g[i]||g[i-1]>g[i]||g[i-2]>g[i-1]))
     
    
   

    

     

    
    

     

       dp1[i]=dp[i-2]+2 ;
     
    
   

    

     

    
    

     
 else if(g[i-1]<g[i])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       dp1[i] = max(dp1[i],dp[i-1]+1) ;
     
    
   

    

     

    
    

     

       dp1[i] = max(dp1[i],dp1[i-1]+1) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else dp1[i]=2 ;
     
    
   

    

     

    
    

     

       ans = max(dp1[i],ans) ;
     
    
   

    

     

    
    

     

       ans = max(dp[i-1]+1,ans) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 cout<<ans<<endl ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 while(~scanf("%d",&n))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       ans = 0 ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     
 scanf("%d",&g[i]) ;
     
    
   

    

     

    
    

     

       init() ;
     
    
   

    

     

    
    

     

       solve() ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/37989019