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$粒子的结果。

代码

Submission #113013803 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论