塔子哥学算法
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
相关推荐
点赞 评论 收藏
分享
查看22道真题和解析 点赞 评论 收藏
分享
点赞 评论 收藏
分享
CVTE公司福利 339人发布 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 腾讯求职进展汇总 #
369699次浏览 3008人参与
# 面试常问题系列 #
7659次浏览 245人参与
# 神州信息求职汇总 #
40591次浏览 285人参与
# 职场新人生存指南 #
235839次浏览 5977人参与
# 2025退税开始啦 #
12924次浏览 228人参与
# Offer比较，你最看重什么？ #
131855次浏览 852人参与
# 传音控股求职进展汇总 #
5660次浏览 35人参与
# 机械人选offer，最看重什么？ #
71011次浏览 464人参与
# 长江存储求职进展汇总 #
42477次浏览 215人参与
# 求职遇到的搞笑事件 #
88646次浏览 646人参与
# 打工人的工作餐日常 #
26244次浏览 226人参与
# 职场中你干过哪些“蠢”事 #
89587次浏览 471人参与
# 通信/硬件求职避坑tips #
39799次浏览 328人参与
# 面试被问第一学历差时该怎么回答 #
100479次浏览 631人参与
# 有哪些越早知道越好的职场道理？ #
21148次浏览 834人参与
# 安克创新求职进展汇总 #
18314次浏览 144人参与
# 推荐一首陪你工作的歌吧 #
10526次浏览 84人参与
# 面试被问期望薪资时该如何回答 #
205546次浏览 1246人参与
# 招银网络求职进展汇总 #
93751次浏览 601人参与
# 那些我实习了才知道的事 #
164496次浏览 1390人参与
# 非技术岗投递进展 #
116846次浏览 974人参与