暴力枚举每个骰子选或不选即可。
我们考虑一个 dp。
我们设 fi,j,kf_{i,j,k}fi,j,k 表示前 iii 个骰子选了 jjj 个且和为 kkk 的方案数。
转移只要枚举这一个骰子是啥就好了。
复杂度 O(n4)O(n^4)O(n4)。
不难注意到转移的是一段区间,我们使用前缀和优化 dp 即可做到 O(n3)O(n^3)O(n3)。
然后我们注意到此时空间不太够用的样子,我们使用滚动数组并将一些值开成 int 即可通过这个题。
一点也不卡常。
注册一个 CZOJ 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 CZOJ 通用账户