编程介的小学生 2017-08-24 10:34 采纳率: 20.5%
浏览 807
已采纳

Maximize Game Time

Jack has got a new game of Super Mario recently. There are n castles in the game, and Princess Peach has been kidnapped by the King Koopa and enjailed in castle n - 1 (0-based). The King Koopa has Son Koopas, and the Son Koopas has Grandson Koopas, and the Grandson Koopas has Great-Grandson Koopas... The whole Koopa family is taking possession of these n castles, and there is exactly one Koopa in each castle and the King Koopa is in castle n - 1. Super Mario's task is to conquer these castles and save Princess Peach.

Each time, Super Mario can freely choose an unconquered castle and go in to fight with the Koopa. Super Mario has time Ti to conquer castle i and beat the Koopa in it. If Super Mario fails to conquer the castle or fails to do that within the time limit, the game is over. Otherwise, the defeated Koopa will go to seek the Father Koopa for help. If any Koopa has two or more Son Koopas beaten by Super Mario, he will get angry. Super Mario has to go to the castle of the angry Koopa and beat him immediately; otherwise the Princess Peach will be killed. If castle n - 1 is conquered and King Koopa is defeated, the game will also end, but with triumph and Princess Peach saved.

Jack loves this game a lot, but he has to prepare for the upcoming ACM/ICPC. So he guarantees to himself that he only plays the game once a month. However, Jack really loves playing game and hates programming, he wants to maximize the time he can spend on the game without breaking his promise.

Input
The input consists of multiple test cases.

Each test case starts with a number N (0 < N <= 1000) in a single line, the number of castles and Koopas. There are two lines following and each contains N numbers. The first line is N numbers, Ti (0 < Ti <= 100) for Super Mario to conquer castle i. The second line is N numbers of Pi (-1 <= Pi < N), the castle (0-based) in which the Parent of each Koopa resides. -1 means that there is no parent for him, and the last number will always be -1, since King Koopa has no Parent Koopa.

The input ends with 0(zero), which should not be processed.

Output
Output the maximal time Jack can play in a single line for each test case.

Sample Input
5
1 2 3 4 5
4 4 4 4 -1
5
2 2 2 2 2
1 2 3 4 -1
9
1 1 1 1 1 1 1 1 1
6 6 6 7 7 7 8 8 -1
0

Sample Output
12
10
8

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-08-27 16:42
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能