Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int mentos[1000];
- int memoria[1000][1000];
- int backtracking (int e, int d, int mov)
- {
- if (e<=d)
- {
- if (mentos[e]==mentos[d])
- return (backtracking (e+1, d-1, mov+1));
- else
- {
- int min1, min2;
- if (memoria[e+1][d]<0)
- memoria[e+1][d]=backtracking (e+1, d, mov+1);
- min1=memoria[e+1][d];
- if (memoria[e][d-1]<0)
- memoria[e][d-1]=backtracking (e, d-1, mov+1);
- min2=memoria[e][d-1];
- return (min(min1, min2));
- }
- }
- return mov;
- }
- int main ()
- {
- int t, n, ct=0;
- scanf ("%d", &t);
- while (t--)
- {
- scanf ("%d", &n);
- for (int i=0; i<n; i++)
- scanf ("%d", &mentos[i]);
- for (int i=0; i<n; i++)
- for (int j=0; j<n; j++)
- memoria[i][j]=-1;
- printf ("Caso #%d: %d\n", ++ct, backtracking(0, n-1, 0));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement