111 History Grading
http://acm.uva.es/p/v1/111.htmlLo primero es obtener la secuencia correcta, e ir procesando una a una las siguientes secuencias respuesta.
Debemos generar el orden relativo de cada secuencia respuesta respecto a la correcta, y en ella buscar la Maxima Subsecuencia Incrementada (Longest Increasing Subsequence).
Primero hay que tener en cuenta una trampa de este problema, ya que parece que pone el orden a contestar, cuando lo que pone es el rango de cada evento
Si pone
4312 en un caso de prueba, eso significa que el primer evento esta en cuarto lugar , el 3 que el segundo evento esta en tercer lugar, el 1 que el tercer evento esta en primer lugar y el 2 que el cuarto evento esta en primer lugar.
Tras esto, se "traduciria" 4312 a 3421.
Si el correcto traducido es 321 y la respuesta traducida es 312, el orden relativo sera 132
Tras obtener los ordenes relativos a las contestaciones, se les debe aplicar un algortimo LIS(Longest Increasing Subsequence).
Aqui teneis un ejemplo de LIS
int lis(int s1[],int tam)
{
int i,j;
int max=0;
int mejores[21];
for(i=0;i<tam;i++)
{
mejores[i]=1;
}
for(i=tam-1;i>=0;i--)
{
for(j=i+1;j<tam;j++)
{
if ( s1[j] > s1[i] )
{
mejores[i] = maximo( mejores[i] , mejores[j]+1 );
}
}
}
for(i=0;i<tam;i++)
{
if(mejores[i]>max)
{
max=mejores[i];
}
}
return max;
}
Portal
Suscribete
Programación
