塔子哥学算法
2020-05-02 01:39 Fleet AntiSubmarine Warfare Training Center (San Diego) C++
关注
有点组合数学那味。计数问题最重要的就是对集合的划分要不重不漏吧。这个题我是这么划分的：
第一行一定要填一个位置。所以枚举第一行填的位置。
设f(x , k)为x*x的网格，第一行填涂第k位的方案数。那么答案就为f(x) = f(x,1) + ... + f(x , x).
若k = 1.那么第一行第一列都不能填了，问题化简成f(x - 1).
k != 1 时，根据对称的要求，位置 (1 , k) 与 (k , 1) 都被填了.那么行和列都会少两个项。剩下来x - 2 行 x - 2 列。所以问题化简成f(x - 2) .. 推荐画画图就出来了.
所以递推式为: f(x) = f(x - 1) + (x - 1) * f(x - 2).
然而比赛的时候并没有这么做细的分析。。。画画图就找得到递推式了.
查看原帖
点赞 1
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
2025-12-14 03:38
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 我的付费上班经历 #
2699次浏览 61人参与
# 如果不上班，你会去做什么 #
1165次浏览 47人参与
# MiniMax求职进展汇总 #
1171次浏览 25人参与
# 参加哪些竞赛对找工作有帮助？ #
1538次浏览 31人参与
# 工作压力大，你会干什么？ #
1289次浏览 41人参与
# 为了入行xx岗，我学了__ #
968次浏览 17人参与
# 职场新人体验 #
160005次浏览 1141人参与
# 你们的毕业论文什么进度了 #
1235096次浏览 9913人参与
# 拿到offer之后，可以做些什么 #
84213次浏览 438人参与
# 硬件/芯片公司工作体验 #
142351次浏览 946人参与
# 你觉得面试是靠实力还是靠运气 #
27323次浏览 305人参与
# 当你面对裁员会如何？ #
353072次浏览 2857人参与
# 生物制药/化工校招攻略 #
72985次浏览 338人参与
# 牛客十周岁生日快乐 #
204005次浏览 1914人参与
# 哪些公司在招寒假实习？ #
25018次浏览 348人参与
# 这些公司卡简历很严格 #
84259次浏览 379人参与
# 聊聊你的职场新体验 #
311297次浏览 1842人参与
# 硬件人秋招进展 #
265328次浏览 3967人参与
# 招聘要求与实际实习内容不符怎么办 #
150399次浏览 891人参与
# 秋招开了，你想投哪些公司呢 #
968372次浏览 11391人参与
# 快手工作体验 #
296776次浏览 2896人参与