El Problema de las Vacas
Cesar Liza Avila
1
Enunciado
• Se tienen 2 vacas que deben alimentarse. Se coloca bloques de
pasto en fila para alimentarlas.
• Las vacas solo pueden comer el pasto que se encuentra en uno de
sus extremos
• La primera de ellas, una vaca inteligente desea aplicar una estrategia
que le permita comer mas pasto.
• La segunda come el bloque de pasto mas grande que se encuentra
en uno de los extremos.
• Implemente la estrategia de la 1ra vaca.
...
César Liza Avila
2
Sea Tabla(i, j) la cantidad de pasto que puede comer la vaca 1
cuando empieza a comer con bloques entre i hasta j.
i, i+1, i+2, . …..…, j-2, j-1, j
La vaca 1, tiene dos alternativas
1) Come pi y luego come lo que pueda comer entre lo que queda
Pero que le queda?
Pues si pi+1>pj, la vaca 2 come pi+1, dejando
tabla(i,j) = pi + tabla(i+2, j)
i, i+1, i+2, . … . . …… , j-2, j-1, j
Pero si pi+1<pj, la vaca 2 come pj, dejando:
tabla(i,j) = pi + tabla(i+1, j-1)
i, i+1, i+2, . … . . …… , j-2, j-1, j
César Liza Avila
3
2) Come pj y luego come lo que pueda comer entre lo que queda
Pero que le queda?
Pues si pi>pj-1, la vaca 2 come pi, dejando
tabla(i,j) = pj + tabla(i+1, j-1)
i, i+1, i+2, . … . . …… , j-2, j-1 j
Pero si pi<pj-1, la vaca 2 come pj-1, dejando:
tabla(i,j) = pj + tabla(i, j-2)
i, i+1, i+2, . … . . …… , j-2, j-1
César Liza Avila
j
4
Condición Base:
Si n=2 bloques
tabla(i, i+1) = max(pi, pi+1)
Si pi>pj-1
pj + tabla(i+1, j-1)
Si pi+1>pj
pi + tabla(i+2, j)
tabla(i,j) = max
Si pi+1<pj
pi + tabla(i+1, j-1)
César Liza Avila
,
Si pi>pj-1
pj + tabla(i, j-2)
5
# include <iostream.h>
# include <iomanip.h>
void llenaTabla(int n, int tabla[ ][MAX])
{ int i,j;
for (i=0; i<n; i++)
for (j=0; j<n; j++)
tabla[i][j] = 0;
}
#define MAX 100
#define max(a,b) ((a)>(b))?(a):(b)
void impTabla(int tabla[][MAX], int n)
{ int i, j;
cout<<" ";
int vacas(int P[], int n);
for (i=0; i<n; i++)
void llenaTabla(int n, int tabla[][MAX]);
cout<<setw(5)<<i;
void impTabla(int tabla[][MAX], int n);
cout<<endl<<endl;
for (i=0; i<n; i++)
void main(void)
{
{
cout<<"i="<<i<<" ";
int P[ ]={2, 2, 1, 5, 3, 8, 7, 3} ;
for (j=0; j<n; j++)
cout<<"Si la 1ra vaca es inteligente come:“
cout<<setw(5)<<tabla[i][j];
<<vacas(P, 8)<<endl;
cout<<endl;
}
}
}
César Liza Avila
6
int vacas(int P[ ], int n)
{ int i;
int pi, pj;
int tabla[MAX][MAX];
llenaTabla(n, tabla); // no es necesario
for(i = 0;i< n-1; i++)
tabla[i][i+1]= max (P[i], P[i+1]);
for(int d=3; d<n; d=d+2)
for(int i=0; i<n-d; i++)
{ int j=i+d;
if( P[j]> P[i+1]) pi = tabla[i+1][j-1];
else pi = tabla[i+2][j];
if (P[i]< P[j+1]) pj = tabla[i][j-2];
else pj = tabla[i+1][j-1];
tabla[i][j] = max (P[i] + pi, P[j] + pj);
}
impTabla(tabla, n); // no es necesario
return tabla[0][n-1];
}
César Liza Avila
7
Vaca 1: 3 + 8 + 5 + 2 = 18
Vaca 2: 7 + 3 + 2 +1 = 13
César Liza Avila
8
PD:
Este problema es similar 3379-Two Ends.
http://acmicpc-livearchive.uva.es/nuevoportal/
Los movimientos de la vaca que usa la
estratagia de tomar el mayor de los
extremos debe ser llenado en las
diagonales que estan vacias.
César Liza Avila
9
Descargar

El Problema de las Vacas