大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/188320.html原文链接：https://javaforall.net
