P4731 题解

· · 题解

题意

对于一个 n 局的保龄球的分数记录，其中有一些位置是未知的，求有多少种将未知的位置填上值的方式使得存在一个局面得到这个分数记录。n\le 10。

思路

一个自然的想法就是记 dp_{i,j} 表示考虑了前 i 局，前面累计分数 j 分的方案数。然而这么记录的问题在于一局的分数不仅仅由它自己决定，还和后面的分数有关。但由于数据范围特别小，所以不妨暴力一些，由于至多后面两次投掷的分数会影响前面的得分，所以记 dp_{i,j,x,y} 表示前 i 局累计分数为 j，下一局的分数需要为 x，下两局分数之和需要为 y 的方案数。这里 x\in[0,10],y\in[0,20]，如果没有 x 或 y 的限制则记为 11 和 21 即可。

考虑这个 dp 如何转移。首先最后一局很特殊，所以最后算答案的时候单独考虑即可。对于前面的局，枚举这一局的得分（包含奖励分），以及两次投掷的分数分别是什么。设这局的得分为 d，则这里分为三种情况转移：

  1. 这一局是一个 strike：必须满足 x=10/11，且 y\ge 10。此时转移过后 x 的限制没了，y 被减去了一个 10 变成了 x 的限制，又增加了一个 y 的限制，所以 dp_{i,j,x,y}\to dp_{i+1,j+d,y-10,d-10}。
  2. 这一局是一个 spare：枚举第一局的得分 a，则必须满足 x=a/11，且 y=10/21。这次转移由于有两次投掷，所以 x,y 的限制都没了。又增加了一个 x 的限制，所以 dp_{i,j,x,y}\to dp_{i+1,j+d,d-10,21}。
  3. 其它情形：枚举两局的得分 a,b，则必须满足 x=a/11，且 y=a+b/21。由于没有奖励分了，所以必须有 d=a+b。此时 dp_{i,j,x,y}\to dp_{i+1,j+d,11,21}。

然后处理最后一局的情形，这里和前面转移的方式是类似的，直接按照题面里给出的最后一局的 7 种情况分别枚举一下，根据前两次投掷的结果判定一下前面状态中 x,y 的合法性，然后计入答案即可，不再赘述。考虑一下这么做的复杂度。一局的得分显然至多是 30，所以总得分至多是 300，记 k=30,d=10，则复杂度 O(n^2k^2d^4)，虽然常数很小，但不能通过。

注意到瓶颈在于普通转移的第三种情形需要枚举两个得分，但由于此时 d=a+b，所以确定了 a 就确定了 b。这样复杂度优化至 O(n^2k^2d^3)，且常数很小。其实还可以根据合法条件省去一些枚举量，但是这样已经足够通过，且实现起来比较清楚。

代码