首页 > 火柴排队
开通博客写题解
头像 __故人__
发表于 2020-09-13 15:55:40
分析 考虑如果一个数有选择，那么可能会影响它的也必须选择。所以这个就是个计数 了。可以写个类似背包的转移来算出所有的可能方案，最后答案再除以所有方案数就好了。时间复杂度为 。当然你可以滚动数组优化空间。 一些细节 表示可以选 个人时的合法方案数，由于从 转移过来的，所以可以滚动数组优化。 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 氧气少年Kevin
发表于 2022-07-14 10:03:21
牛客7329D - 火柴排队 链接：https://ac.nowcoder.com/acm/contest/7329/D 知识点：概率、古典概型、组合计数、分组背包DP 难度：紫 题意 给出一个长度为 nnn 的序列，序列中的数字两两不同。 现在随机从中选择 kkk 个元素，将它们的数值 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”