algorithm - SPOJ ANARC07G 让我们去看电影吧

Question

在this问题我们必须找到所需的单人票和家庭票的数量，以使价格最低。如果许多安排的价格相同，则打印最低票价的安排。

问题陈述阿克梅斯坦的电影院有两种类型的门票:单人票仅供一个人使用，而家庭票则允许 parent 和他们的 child 进入电影院。不用说，家庭票的价格总是高于单人票，有时甚至高达单人票的五倍。

对于家庭来说，决定购买哪种票务安排最经济是一个很大的挑战。例如，右图所示的家庭有四种票种可供选择:七张单人票；两张家庭票；一张家庭票(adam、bob、cindy)加上其余四张单人票；或者，一张家庭票(供鲍勃和他的四个 child 使用)加上供其余两个 child 使用的单人票。

编写一个程序来确定哪种票价最低。如果有多个这样的排列，打印出票数最少的排列。

我的DP方法如下:-

1. 制作家谱。

2. 每个节点都应该有字段 min_tickets(即最小票数)和 min_price(即最低价格)。这些字段表示带那个人和他的 child 出去所需的最低金额。此外，还有一些字段表示该过程中涉及的家庭票数(fam_tickets)和单人票数(sin_tickets)。

3. 从叶节点开始。初始化min_tickets=1和min_price=S(即单票价格)，fam_tickets=0，sin_tickets=1.

4. 现在为其他节点考虑他的子孙。 F 是家庭票的价格。对于他们:-

   min_price= min(F + min_price of all grandchildren summed , S + min_price of all children summed)

   如果孙子为 NULL，我们取 min_price=0 和 min_tickets=0

5. 为了找出 min_tickets，我们从给出最低价格的构造中得出它。如果两种形态的价格相同，我们会:-

 if(1+ min_tickets of all grandchildren summed > 1+ min_tickets of all children summed)  
      min_tickets = 1+ min_tickets of all children summed;
      fam_tickets= fam_tickets of all children summed;
      sin_tickets= 1+ sin_tickets of all children summed;
 else  
      min_tickets = 1+ min_tickets of all grandchildren summed;
      fam_tickets= 1+ fam_tickets of all grandchildren summed;
      sin_tickets= sin_tickets of all grandchildren summed;

这个解决方案是否正确？提前致谢。

Answer 1

在你的例子中，你是否考虑过他们购买两张家庭票以获得最大利润的情况？看来在你的解决方案中，在处理adam的节点时，

min_price= min(F + min_price of all grandchildren summed , S + min_price of all children summed)

将不起作用。

我不知道您的实现细节，但这是一个棘手的部分。希望能帮助到你。 :)