大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
题意理解:
http://acm.timus.ru/problem.aspx?space=1&num=1142
有N个对象,问有多少种关系?
问题分析:
用动态规划做:f(a,b) 表示a个对象分成b组的分法。b组的意思是a个对象放到b个篮子里,每个篮子的对象之间是相等关系。
初始值:
f(0,0) = 1; f(0,1…N) = 0; f(1…N, 0) = 0
递归式:
f(a,b) = f(a-1,b) * b + f(a-1, b-1)
f(a-1,b) * b 表示已知a-1个对象放到b个组中,再多一个对象可以放到b组任意一组中,共有b种方法;
f(a-1,b-1) 表示已知a-1个对象放到b-1个组中,再多一个对象时,要保证有b组,那只有将多的一个对象独立成组才可以。
这样,解决了N个对象分成b组的分法,分成b组后,关系是排列数,所以求b组的全排列值,有几组就是组数的阶乘,对于N个对象,它的关系数为f(N,1) * 1! + f(N,2) * 2! + f(N,3) * 3! +… + f(N,N) * N!
其他:
此题一开始使用硬分析,发现无法穷尽2个等于的情况。学到的一点就是脑子不要太累,太累的方法一定不是好方法,管理自己做题的脑力,尽可能思考用简洁有效的思路。
代码链接:
https://github.com/xierensong/learngit/blob/master/timus/t1142.cpp
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/188320.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...