119149_1125*2436

119149_1125*2436题意理解: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(…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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账号...

(0)


相关推荐

  • 数据库的数据模型是网状模型_网状模型的数据结构是

    数据库的数据模型是网状模型_网状模型的数据结构是层次数据模型    定义:层次数据模型是用树状<层次>结构来组织数据的数据模型。    满足下面两个条件的基本层次联系的集合为层次模型    1.有且只有一个结点没有双亲结点,这个结点称为根结点    2.根以外的其它结点有且只有一个双亲结点其实层次数据模型就是的图形表示就是一个倒立生长的树,由基本数据结构中的树(或者二叉树)的定义可知,每棵树都有且仅有一个根节点,其余的…

    2022年10月29日
  • onStart和onResume的区别

    onStart和onResume的区别当Activity被onCreate后就会进入onStart状态,使这个Activity对用户来说呈可见状态,但不能交互。onStart之后调用onResume使得这个Activity获得焦点,排在了所有其他Activity之前,从而获得与用户交互的能力。

  • 单片机八路抢答器计设计_基于单片机的三路抢答器设计

    单片机八路抢答器计设计_基于单片机的三路抢答器设计详细代码讨论加我QQ:1271370903一、设计任务与要求一、题目:8路比赛抢答器二、基本要求:利用8051单片机中断系统,制作一个有8个按键的比赛抢答器。在有人按键时进行对应选手显示。三、设计任务:1.设计硬件电路,画出电路原理图;2.画出程序流程图;3.编制程序,写出源程序代码;4.写出5000字的详细说明书,要求字迹工整,原理叙述正确,会计算主要元器件的一些参数,并选择元器件;5.个人总结。四、参考资料:1.教材;2.单片机实验指导书》**二、方案设计**方案:该系

    2022年10月20日
  • cmd命令怎么切换盘符_windows切换盘符命令

    cmd命令怎么切换盘符_windows切换盘符命令转载于:https://www.cnblogs.com/QMM2008/p/4003039.html

  • DirectX修复工具的详细使用步骤介绍[通俗易懂]

    DirectX修复工具的详细使用步骤介绍[通俗易懂]DirectX修复工具的详细使用步骤介绍@TOCDirectX修复工具是一款系统级工具软件,简便易用,无需安装,可直接运行,下面为大家分享的是DirectX修复工具的详细使用步骤介绍首先我们下载DirectX修复工具,再找到并打开“维护电脑”,在找到并打开“恢复软件”,再点“DirectX修复工具”2.这时候解压之后,这里有两个DirectXRepair.exe修复工具,另一个Direc…

  • 姿态估计与行为识别(行为检测、行为分类)的区别[通俗易懂]

    姿态估计与行为识别(行为检测、行为分类)的区别[通俗易懂]姿态估计和行为识别作为计算机视觉的两个领域,对于新人来说,较为容易弄混姿态估计和行为识别两个概念。 姿态估计(PoseEstimation)是指检测图像和视频中的人物形象的计算机视觉技术,可以确定某人的某个身体部位出现在图像中的位置,也就是在图像和视频中对人体关节的定位问题,也可以理解为在所有关节姿势的空间中搜索特定姿势。简言之,姿态估计的任务就是重建人的关节和肢干,其难点主要在于…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号