Codeforces Round #711 Planar Reflections - Compression DP

Solution

Compression DP.

Let the particles with lifetime $i$ pass through all the planes first. And then calculate the particles with lifetime $i-1$.

We can notice that the particle with lifetime $i$ runs in the same direction, and is opposite to the direction of the particle with lifetime $i-1$.

Define $dp[i][j]$ to represent the number of times the $j$th board is shot after the particle with the life of $i$ passes through all the boards. Let the current direction be $order$.

So $dp[i][j]=dp[i][j-order]+dp[i+1][j-order]$. Which means, $dp[i][j]$ depends on the number of times the previous board was pierced and the number of particles reflected by the previous board $i+1$.

Code: