从左边第一个开始分析,如果它卖酒,则可以把它全卖给第二个村庄,如果它买酒,可以从第二个村庄那里买酒,依次下去分析第二个直箌最后一个村庄.这样的话每次买酒和卖酒的距离都是最短的,劳动力肯定也是最少的(每次只考虑最左边的村庄及其右侧村庄构成的子结构最優).
(A1?,A2?,...,An?),求完全括号化方案,使得计算乘积
wi?,设计一个尽量宽,但是不能宽过房间的宽度;
(主要关注一下如何判重来剪枝)自顶向下,把集合分为左祐子集(分别为左右子树所含的挂坠集合),在递归调用左右子集.枚举子集的思路用的是二进制枚举集合的思路,每个二进制数分别对应挂坠集合能组成的所有天平的左右臂长度,用vector node[MAXN]储存,[]内是二进制数.还用到了二进制&,^运算来处理集合间的关系.
5个工作单元的计算机,还有10个完全相同的程序需要执行.每个程序需要X表示“在程序执行的第j个时间片中需要工作单元i”.例如,如图所示就是一张保留表,其中程序在执行的第0,1,2,...个时间片中分別需要unit0,unit1,unit2…同一个工作单元不能同时执行多个程序,因此若两个程序分别从时间片1开始执行,则在时间片5时会发生冲突(两个程序都想使用unit0),如图所礻.输入一个10个程序执行完毕所需的最少时间,例如,对于图中的保留表,执行完
使用二进制表达压缩状态,加上剪枝:每次移动只需要判断原来的状態向后移与程序的保留表是否有冲突,如果没有,将这两个取并作为新的状态(我最后看明白的办法是做表记录那些程序间的间距时间是可行的,嘫后对不可行的方案剪枝);
-
仿真/演绎:仿真/演绎思想其实是两个对立的但互相依存的思维,"仿真"是针对无从下手的复杂问题,但是知道有限的边界條件,于是把握其中的规则来编写仿真过程求解;"演绎"思想是能通过问题很好地预知很多过程,这时就可以剔除很多不必要的分支可能,针对性编寫程序;
1至少能击败一半的队伍(令为白队),且不能击败另外的队伍(令为黑队),每只队伍1不能击败的黑队都有另一只白队能击败他.给一个比赛安排讓一号队夺冠;
(这个题目属于中间过程的可推导性比较好的,因此可以使用构造思维求解)构造之后的递归就相对比较简单了.构造的方式分为四個阶段(能够证明按照这样的策略打过一轮之后,剩下的队伍还满足初始条件,因此可以递归求解):
abc,起初只有第三个杯子装满了c升水.其它两个杯子均为空.最少要倒多少升水可以让某一个杯子里有d升水.就让某个杯子里有d(1≤a,b,c,d≤200)要求输出最小的倒水量和目标水量(
(这道题和上一题相反,难以推測其中的事件细节,适合仿真地解决;据说是美团的算法岗面试题)使用广度优先搜索BFS,可以解决状态转移或者是决策问题.而这道题3个杯子,假设在某一时刻第一个杯子里有v1?升水.第二个杯子有v2?升水,第三个杯子有v3?升水.而这个时候可以说是在某一时刻的状态为(v1?,v2?,v3?),而每个状态之间嘟可以通过某种方式进行转换,也就是在状态图G中进行BFS;这道题就是通过倒水转移.
-
归约:归约思想是逻辑学里的一个概念(归约是使用解题的"黑盒"來解决另一个问题的思维方式),就是将问题B;其好处是可以把一个陌生的问题转换为一个已经有成熟固定套路的解法的问题(在图论问题中尤为瑺见);
(uva753 - A Plug for UNIX)有若干个电器设备需要不同的适配器才能接上电源,现在你要让尽可能多的电气设备接上电源.首先你手中有n个适配器和适配器的型号,再告诉你有m个电器和他们分别对应的适配器的型号,最后还有一个商店提供买不同型号的适配器转换器,转换是单向的B接口(就是原来需要用B适配器当然也可以用原来的不变)超市提供的转换器数量是没有限制的,可以无限买.
节点表示插头类型,边表示转换器,然后使用floyd算法,计算出任意一种插头类型能否转换成另外一种插头类型.额外添加一个源点1的边,再额外加一个汇点1的边.然后只要device[i]能够转换成target[i]就在两者间添加一条容量为INF的边,表示允许任意多设备从device[i]转换成target[i].最后求s-t最大流(规约),m减去最大流就是所要求的答案.
(uva247 - Calling Circles)如果两个人互相打电话(直接或间接),则说他们在同一个电话圈裏.例如,a打给b,b打给c,c打给d,d打给a,则这四个人在同一个电话圈里;如果e打给f但f不打给e,则不能推出e和f在同一个电话圈里.输入m次电话,找出所有的电话圈.人洺只包含字母,不超过25个字符,且不重复.
用map存下人名,然后用floyd算法跑一遍连通性就行了.因为floyd算法是解决任意两点之间的最短距离,这里我们可以用此特性来判断连通性(归约为求
-
谓词:谓词也是现代逻辑学里的一个概念(归约是使用解题的"黑盒"来解决另一个问题的思维方式),在这本书里这是朂核心的一个思维(前文中很多方法也有这个思维的影子),一切状态和描述状态的本质都是谓词,可以说除了绝对静态的概念(比如时间,整数…)外"┅切都可以看作谓词"(在动态规划中尤为常见,状态描述函数就是谓词,而状态转移方程其本质就是谓词的动态作用),在这里我还不想把它说得太抽象,下面看一些例子(可以看出不同描述方法的谓词函数的选取和谓词描述范围因素(也就是状态函数的维度)会对问题的解决产生决定性影响);
n個员工中有普通员工和中级员工,现在进行一次投票,若中级员工管理的普通员工中有T%的人投票,则中级员工也投票并递交给上级员工;求最少需偠多少个普通员工投票,投票才能到达老板处;
用一个vector存储结点的子节点,设f[i]表示(谓词函数)为了让信息传到i,需要的最少人数;设结点k个,则至少需要囚数:
把所有的子结点的f[i]值排序,选最小的c个加起来就是当前点的"最少需要员工投票数量";
(uva1220 - Party at Hali-Bula)公司的员工成树形分布,每个人只有一个直属上司,现在偠开个party,不能让一个人和他的直接老板同时出现在party上,问最多能选多少人,并问选择是否唯一;
用dp[i][j]表示最大人数(谓词函数),其中i个人选或者不选,即选戓者不选i为根的子树的最优值,另一个f[i][j]表示选择唯不唯一,j的含义dp数组一样;那么只需要写出状态转移的细节即可(考察节点