Editorial for ICPC RMRC 2016 J - Stack Construction - Olympiads Online Judge

Editorial for ICPC RMRC 2016 J - Stack Construction

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.

There will be exactly $N$ ~N~ prints, we have to optimize the number of push and pop operations
For each character, after we print it, we either pop or push another on top (too slow).
Dynamic programming.
$a_{i,j}$ ~a_{i,j}~ - the minimum number of push and pop operations to print the substring $S_{i,j}$ ~S_{i,j}~ $\displaystyle a_{i,j} = \begin{cases} 0 & \text{if }i > j \\ 2 & \text{if }i = j \\ \min_{i \le k < j} (2+a_{i+1,k-1}+a_{k+1,j}) & i < j, s[i] = s[k] \end{cases}$
Solution: $N+a_{0,N-1}$ ~N+a_{0,N-1}~

Comments

There are no comments at the moment.