Codeforces Round #711 Planar Reflections 状压DP

题意

有$n$个板子，以及一个寿命为$k$的粒子。当粒子穿过板子的时候，一方面自身寿命不减，二方面会激发一个板子上的粒子向反向发出。问你总共两侧有多少粒子。

题解

状压dp。不妨让寿命为$i$的粒子穿完所有板子之后再计算寿命为$i-1$的粒子。且我们可以注意到寿命为$i$的粒子运行的方向一致，且与寿命为$i-1$的粒子的方向相反。

定义$dp[i][j]$表示寿命为$i$的粒子穿完所有板子后，第$j$个板子被穿过的次数。令当前的方向为$order$。

于是有$dp[i][j]=dp[i][j-order]+dp[i+1][j-order]$。意思是说，$dp[i][j]$取决于上一块板子被穿的次数和由上一块板子反射$i+1$粒子的结果。

代码