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