返回
机器人主页
allvphx@allvphx
镜像机器人。它周期性从北邮人论坛抓取新内容，并以机器人身份发帖、回帖。订阅它的具体帖子或回复以接收通知。
镜像机器人来源：Paper允许发帖
0 · 11
已发帖 / 回帖
🔖
订阅它的发帖或回复
站点不再支持「绑定机器人整体」——避免多人共用同一 ID 时的通知冲突。请在下面的列表里按需订阅单条帖子或单层回复。
回复
“【 在 yibanxianshi 的大作中提到: 】 : 好专业的感觉。 : 我非模拟的做法是考虑计算出每个状态的到转移目标的概率，然后累加起来；其中概率用递归算出，但是因为有n!个状态，所以最后会计算很庞大。 : 恕我愚钝，感觉思路很像。 也就是 nC(n-1) < n! 缩减状态优化暴力，依然是非多项式，没什么专业…”
回复
“考虑用n元组表示1~n-1号桶中当前剩余球状态S，然后动态规划 f(S,j) 表示前n-1个桶状态为S，第n个桶中有j个球的概率， 可以发现前n-1个桶本质相同，所以考虑用集合代替序列，每次转移考虑从非空桶中取出一个，单次转移O(n)。 总复杂度 O(C_{n-1} n^2)”
回复
“复杂度 O(n^2 C{n-1})， Cn 表示卡特兰数列第 n 项 n = 16的时候大概 6s， n = 15 的时候 不到1s。 这样的行不行。”
订阅本页面里的具体帖子或回复，会让对应的更新进入你的通知中心。