SHARE
TWEET

Untitled

a guest Dec 6th, 2014 383 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. int N; //Number of ints
  7.  
  8. bool palindrome(int X[], int low, int high)
  9. {
  10.  if(high == low)
  11.  return 1;
  12.  
  13.  int mid = (high - low)/2;
  14.  for(int i = 0; i <= mid; i++)
  15.  {
  16.     if(X[low + i] != X[high - i])
  17.         return 0;
  18.  }
  19.  return 1;
  20. }
  21.  
  22.  
  23.  
  24. int main()
  25. {
  26.  ios::sync_with_stdio(0);
  27.  
  28.  cin >> N;
  29.  
  30.  int a[N];
  31.  int bestpal[N + 1];
  32.  
  33.  for(int i = 0; i < N; i++){
  34.  cin >> a[i];
  35.  bestpal[i] = N + 1;
  36.  }
  37.  bestpal[N] = 0;
  38.  
  39.  for(int i = N - 1; i >= 0 ; i--)
  40.  {
  41.     for(int j = i; j < N; j++)
  42.         {
  43.         if(a[i] == a[j])
  44.         {
  45.         if(palindrome(a, i, j))
  46.         bestpal[i] = min(1 + bestpal[j+1],bestpal[i]);
  47.         }
  48.         }
  49.  
  50.  }
  51.  
  52.  cout << bestpal[0];
  53.  
  54.  
  55.  
  56. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top