CF295C

· · 题解

首先说明

本文思路借鉴于此

题目大意

### 基本思路 刚开始我认为这题是个数学题，运用“慢者相伴，快者来回”的方法，先让 $100$ 的人和 $50$ 的人过去，再将 $50$ 的人送回来，可这样还要考虑 $k$ 的重量，太麻烦了。 ### 题目思路 这道题只追求最小值，而不纠结中间过程，是一道动态规划题。 #### 状态 这道题我们首先求方案。在这里，$100$ 人和 $50$ 坐与 $50$ 人和 $100$ 坐是无关的，所以它是一个组合数。之后我们再定义 $f_{a,b,c,d}$ 表示 $C_a^c$ 与 $C_b^d$ 之和（从 $a$ 个人中选择 $c$ 个人，同时在 $b$ 个人中选择 $d$ 个人可能的方案） 我们定义 $dp_{i,j,k}$ 表示第 $i$ 次来回，船上 $j$ 个 $50$ 千克的人与 $k$ 个 $100$ 千克的人。 #### 状态转移方程 既然要运过去，还要运过来，就要有两个状态转移方程，它们分别是： - 运过去： $$dp_{i,j-a,k-b}=dp_{i,j-a,k-b}+f_{j,k,a,b}\times dp_{i-1,j,k}$$ - 运回来： $$dp_{i+1,j+a,k+b}=dp_{i+1,j+a,k+b}+f_{x-i,y-j,a,b}\times dp_{i,j,k}$$ 最后，记得取模。 #### 边界条件 由于这里的 $dp_{i,j,k}$ 是用来辅助 $f_{a,b,c,d}$ 一起来求方案数，所以我们边界条件就是： $$dp_{0,x,y}=1$$