Advertisement
Kingreey

Mentos

Mar 2nd, 2015
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int mentos[1000];
  5. int memoria[1000][1000];
  6.  
  7. int backtracking (int e, int d, int mov)
  8. {
  9.     if (e<=d)
  10.     {
  11.         if (mentos[e]==mentos[d])
  12.             return (backtracking (e+1, d-1, mov+1));
  13.         else
  14.         {
  15.         int min1, min2;
  16.         if (memoria[e+1][d]<0)
  17.             memoria[e+1][d]=backtracking (e+1, d, mov+1);
  18.         min1=memoria[e+1][d];
  19.         if (memoria[e][d-1]<0)
  20.             memoria[e][d-1]=backtracking (e, d-1, mov+1);
  21.         min2=memoria[e][d-1];
  22.         return (min(min1, min2));
  23.         }
  24.     }
  25.     return mov;
  26. }
  27.  
  28.  
  29. int main ()
  30. {
  31.     int t, n, ct=0;
  32.     scanf ("%d", &t);
  33.     while (t--)
  34.     {
  35.         scanf ("%d", &n);
  36.  
  37.         for (int i=0; i<n; i++)
  38.             scanf ("%d", &mentos[i]);
  39.  
  40.     for (int i=0; i<n; i++)
  41.         for (int j=0; j<n; j++)
  42.             memoria[i][j]=-1;
  43.  
  44.         printf ("Caso #%d: %d\n", ++ct, backtracking(0, n-1, 0));
  45.     }
  46.  
  47.     return 0;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement