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}$ $a_{i, j} = {\begin{cases} 0 & if i > j \\ 2 & if i = j \\ min_{i \leq 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.