fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int ar[310] ,dp[310][310];
  4. int main(){
  5.     int n;
  6.     while(scanf("%d",&n),n){
  7.         memset(dp,0,sizeof(dp));
  8.         for(int i=1;i<=n;i++){
  9.             scanf("%d",ar+i);
  10.             if( i>=2&&abs(ar[i]-ar[i-1])<=1 ) dp[i-1][i] = 2;
  11.         }
  12.         for(int i=3;i<=n;i++){
  13.             for(int j=1;j+i-1<=n;j++){
  14.                 int L=j ,R=j+i-1 ;
  15.                 int upL=dp[L][R-2], upM=dp[L+1][R-1], upR=dp[L+2][R];
  16.                 if( abs(ar[R-1]-ar[R])<=1 ) upL+=2;
  17.                 if( abs(ar[L]-ar[L+1])<=1 ) upR+=2;
  18.                 if((R-1)-(L+1)+1 == dp[L+1][R-1] &&
  19.                     abs(ar[R]-ar[L])<=1) {upM+=2;}
  20.                 upL = max(upL,dp[L][R-1]), upR = max(upR,dp[L+1][R]) ;
  21.                 dp[L][R] = max(upM,max(upL,upR));
  22.             }
  23.         }
  24.         printf("%d\n",dp[1][n]);
  25.     }
  26. }
Runtime error #stdin #stdout 0s 3832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BVdl8h
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!