fork(1) download
copy 
  1. //Sarvagya Agarwal
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define rep(i,a,b) for(int i=a;i<=b;++i)
  5. #define is(X) cout<<#X<<" is "<<X<<endl
  6. #define ff first
  7. #define ll long long
  8. #define ss second
  9. #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  10. #define pb push_back
  11. #define mp make_pair
  12. #define openin freopen("input.txt","r",stdin)
  13. #define openout freopen("output.txt","w",stdout)
  14.  
  15. int arr[550],n;
  16. int dp[550][550];
  17. int solve(int i,int j)
  18. {
  19.     if(i>j){
  20.         return dp[i][j]=0;
  21.     }
  22.     if(i==j)
  23.     {
  24.         return dp[i][j]=1;   
  25.     }
  26.     if(dp[i][j]!=-1)return dp[i][j];
  27.     int ans = INT_MAX;
  28.     //int a1 = 1 + solve(i+1,j);
  29.     int a1;
  30.     if(dp[i+1][j]!=-1)a1 = dp[i+1][j] + 1;
  31.     else a1 = 1 + solve(i+1,j);
  32.     ans = min(ans,a1);
  33.     if(arr[i]==arr[i+1])
  34.     {
  35.         if(dp[i+2][j]!=-1)ans=min(ans,1+dp[i+2][j]);
  36.         else ans=min(ans,1+solve(i+2,j));
  37.     }
  38.     for(int k = i+2;k<=j;k++)
  39.     {
  40.         if(arr[k]==arr[i])
  41.         {
  42.             //ans = min(ans , solve(i+1,k-1) + solve(k+1,j));
  43.             int a,b;
  44.             if(dp[i+1][k-1]!=-1)a = dp[i+1][k-1];
  45.             else a = solve(i+1,k-1);
  46.             if(dp[k+1][j]!=-1)b = dp[k+1][j];
  47.             else b = solve(k+1,j);
  48.             ans = min(ans,a+b);
  49.         }
  50.     }
  51.     //is(i);is(j);is(ans);
  52.     return dp[i][j] = ans;
  53. }
  54.  
  55. int main()
  56. {
  57.     fast;
  58.  
  59.     int n;
  60.     cin>>n;
  61.     rep(i,1,n)cin>>arr[i];
  62.     rep(i,1,n)rep(j,1,n)dp[i][j]=-1;
  63.     cout<<solve(1,n)<<endl;
  64.     return 0;
  65. }
Success #stdin #stdout 0s 4636KB
comments (?)
stdin
copy 
7
1 4 4 2 3 2 1
stdout
copy 
2
https://ideone.com/885pOQ
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!