Editorial for Juegos de rivalidad

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Denotemos $DP_{i,j}$ ~DP_{i,j}~ como la mejor respuesta que se puede tener a partir de los primeros i juegos del equipo A y de los primeros j juegos del B. Las transiciones son las siguientes:

el juego i de A no es de rivalidad, por lo que $DP_{i,j} = max( DP_{i-1,j} , DP_{i,j} )$ .
el juego j de B no es de rivalidad, por lo que $DP_{i,j} = max( DP_{i,j-1} , DP_{i,j} )$ .
El juego i de A y el j de B son de rivalidad, esto solo e posible si A ganó, B perdió y A anotó mas puntos que B, o si B ganó, A perdió y B anotó mas puntos que A, en este caso $DP_{i,j} = max( DP_{i-1,j-1} + A_i + B_j , DP_{i,j} ).$

Complejidad $O(n^2)$ ~O(n^2)~.

Una solución no polinomial obtendrá 40 puntos, una DP en $O(n^4)$ ~O(n^4)~ obtendrá un poco mas de puntos.

Comments

There are no comments at the moment.