LA3902 Network

题意

给出了一棵树,和一个初始的黑点(VOD服务器),所有边的边权均为1,你要求出最少还要染黑几个点,才能保证每一个白点到最近黑点之间的距离小于等于k。

思路

大概是贪心。

把给出的初始黑点当成树的根部,从根部dfs一次求出所有节点的深度,然后把深度最大的点(如果深度大于k)染黑,之后以这个点为中心dfs一次标记所有能覆盖的点。然后找第一个没有被覆盖的点,染黑,标记。。。直到所有点都被标记。

代码

 

UVa 11729 Commando War

题意

请参考《LRJ大礼包::白》第一章例题2

思路

大概是贪心。

只要交代了任务,部下自己就会给做完了,基于这样的题意我们就可以设计这样的一种贪心策略:优先考虑完成任务时间长的,这样交代完了之后就会有更多的时间可以一边交代任务一边有人完成任务,更有效率。

具体操作就是把完成任务时间从大到小排个序,然后顺着检查一遍。

这个策略的证明在白书上面有提供,大概的证明套路就是说明不用这个策略时得到的答案不会更优,在证明时分类讨论了两种情况。

代码

 

 

 

POJ 3646 The Dragon of Loowater

题意

请参考<LRJ大礼包::白>的第一章例题1.

思路

大概是贪心。因为骑士的能力=能砍多大=花多少钱,这样的话只要排个序,从最便宜的英雄开始检查,从小头开始砍,直到检查完最后一个英雄。

如果没砍死就是没解,否则一定是最优解,这个思维和Kruskal算法是一致的。

代码

 

UVA 12955 Factorial

题意

给出你一个数,问你这个数最少能用多少个数(可以重复)的阶乘表示出来。

思路

使用一种简单的贪心策略:

从一个刚好比给出的数小的阶乘开始,不断尝试减掉较大的阶乘,直到将给出的数减为0 。

这个贪心策略是合理的,因为如果我们当前可以减掉n!,我们减掉(n-1)!一定不如减掉n!优,因为n!=n*(n-1)!,相当于我们多减了n次,所以我们要减掉n!才能保证最优。

代码

 

URAL 2066 Simple Expression

题意

给出三个数,要你求出用这三个数进行加减乘运算可以得到的最小值是多少。

思路

问题规模相当小,可以枚举每一种算术组合。也可以使用一些贪心策略少枚举一些情况,详情请参考下面的代码。

代码

 

SGU 195 New Year Bonus Grant

题意

某厂采用一种奇怪的方式发奖金,给出一个上下级关系树,大BOSS是1号根节点,别的员工都有自己的上司。对于每个员工,它有三种选择,要么接受上级下发的奖金,要么给所有下级发奖金,要么啥都不做(只有傻子才会这样,所以你可以当成没这种选择),大BOSS一定发奖金。只要一个员工选择收奖金,他就得到1000块。

现在要你设计一种方案,使得所有人收到的奖金的总数额最大。

思路

树DP解法

对于每一个节点,都有两种状态:选择收奖金,选择收奖金。

对于选择收奖金的节点的儿子节点,一定不可以选择收奖金。

对于选择发奖金的节点的儿子节点,可以选择收他的奖金,也可以选择发奖金。

这样就可以建立dp数组dp[a][0/1],a是节点对应的编号,0/1表示该节点选择收/发奖金的状态。利用DFS下潜到叶子节点之后,就可以开始树DP了。

状态转移的方程可以参考dfs()方法。

输出路径的话,只要记录下每一次的决策,DP结束之后反查就可以搞定。

贪心解法

引用自JHC23的Blog。

自底而顶遍历,如果自己的上级没有接受奖金(那么就能够把钱给发自己了),而自己也从不增接受奖金则可以获得奖金,同时标记自己和上级。这样下去就可以得到可得到最大奖金。

代码

树DP解法:

 

CodeForces 1A Theatre Square

作为CF的Hello World题,居然会拿爆int这种事坑人。。。

Scroll to top