题目描述

Arthur公司是一个等级森严的公司,它们有着严格的上司与下属的关系,公司以总裁为最高职位,他有若干个下属,他的下属又有若干个下属,他的下属的下属又有若干个下属……现接近年尾,公司组织团拜活动,活动中有一部分是自由舞会,公司的每个职员都有一个搞笑值,现要你制定一套哪些人上台的方案,使得台上所有演员的搞笑值最大。当然,职员们是不会和他们的顶头上司一起上台的。

输入

第一行一个整数N,表示这个公司总共的职员个数。

接下来一行有N个整数,由空格隔开,第i个整数表示职员i的搞笑值Ai(-1327670≤Ai≤1327670)。

接下来N-1行,每行一个1到N的整数,第i个整数表示职员i+1的顶头上司是谁,当然总裁就是职员1。

输出

一个整数,表示台上所有职员搞笑值之和的最大值。

样例输入

7 1 1 1 1 1 1 1 1 1 5 1 4 4

样例输出

5

题解:这是一道树形dp题,很简单,对于每个人抉择选或不选,如果上司选了,他就不选,反之,可选可不选。

 

代码实现:

 

题目描述

明明喜欢Pizza,但总是缺钱。有一天,他在报纸上阅读,他最喜爱的比萨饼店–必胜客,正在对大批新Pizza运行的促销。促销的办法是:在购买一些Pizza后,可能得到一些优惠券,可以对另一些Pizza进行打折,更令人惊喜的是这些优惠券可以结合起来。但是,有一个限制,Pizza必须一个接一个买,而后得到的优惠券也不可能追溯前面已经买过的Pizza。明明想尝试若干新品Pizza,可又没有充足的钱,为了能省一些,明明费劲脑力,就请你帮他计算一下如何购买Pizza,使得其平均价格最低!平均价格是指买到Pizza的总价格/总面积,即单位面积的Pizza的价格。还要注意,“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时,有可能排在后面的某个操作比前面的某个操作先完成。

输入

有多组输入数据。
每组输入数据第一行为m(1<=m<=15).
接下来m行,每行前3个数pi,ai,ni(1<=pi<=10000,1<=ai<=10000,0<=nipi为编号为i的Pizza的价格,ai为编号为i的Pizza的面积,ni为购买i号Pizza能得到ni张优惠券
接下来ni*2个数,分别表示该张优惠券对xi号Pizza打折(1<=xj<=m,i<>xj),折扣为yj(1<=yj<=50)
输入以m=0结束。

输出

输出购买m个Pizza中某一些的最低单位面积价格。保留4位小数。
(如果一个Pizza原价10,得到了一张50和一张20的优惠券,那么购买它实际所需的价值就是10*0.5*0.8=4)

样例输入

样例输出

题解:m<=15,显然这是一道状压DP题,dp[i]可以表示当前状态i的最小花费,在最后或循环中计算面积可求出平均价格即可。

状态转移:对于一个状态i,枚举上一个吃的第j个Pizza,在根据状态i-(1<<j-1)找j可以用的优惠券

代码实现: