BewareMyPower level
获赞
1993
粉丝
54
关注
5
看过 TA
59
中国科学院大学
2019
Java
IP属地:湖北
暂未填写个人简介
私信
关注
2018-09-07 02:12
已编辑
中国科学院大学 Java
0 点赞 评论 收藏
分享
2018-07-04 20:58
中国科学院大学 Java
0 点赞 评论 收藏
分享
2019-09-02 21:34
已编辑
中国科学院大学 Java
看了一圈都没人发,3号笔试的一批很冷么? K种玫瑰花摆在N个位置上,要求每种花至少出现一次,求方法数。K不大于30,N不大于50000。我的思路是先K个位置上各放1种,然后有K!*C(K, N)种,但是发现会有很多重复的可能。于是只能暴力dfs剪枝,只过了20%。
BewareMyPower:感谢楼上回复,我还是太水了,算法练习得少,写得不好。 关于2楼,我通过率是20%而该层主通过率40%的原因,刚才重写时也许找到了,我的代码逻辑错了。比如DFS到第i层,假如K种花都已经放过了,那么就可以不用继续递归了,剩下N-i层每一层都可以放K种花,也就是结果加上K的N-i次方。由于我是按照N=3 K=2来作为示例,所以这里我加上了2的N-i次方。 关于动归的思路,应该是f(n, k) = k*(f(n-1, k-1) + f(n-1, k)。设花的种类为1~k,f(n-1, k-1)可以看作前n-1个位置放置花种1~k-1的种数,然后第n个位置必须放置花种k。由于轮换对称性,第n个位置的花种k可以和任意花种兑换,因此要乘以k。f(n-1, k)则可以看作前n-1个位置就放置了所有的花种,因此肯定和前面的k*f(n-1, k-1)的放置放法是不同的。当然这里也要乘以k,因为第n个位置还是能放置k种花。
投递360集团等公司10个岗位 >
0 点赞 评论 收藏
分享
关注他的用户也关注了:
牛客网
牛客企业服务