首页 > 试题广场 >

蚂蚁森林之王

[编程题]蚂蚁森林之王

热度指数：1986 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

很久很久以前，在蚂蚁森林里住着 $\mathit n$ 只小动物，编号从 $\text 1$ 到 $\mathit n$ 。编号越小的动物能力值越大。现在他们想投票选出一只小动物当森林之王，对于每只小动物来说，如果他有崇拜的对象，那么他可能投票选择自己，或与自己崇拜的对象投相同票；如果他没有崇拜的对象，那么他投票只可能选择自己。
每只小动物只会崇拜能力值比自己大的小动物。
记者小强拜访了这 $\mathit n$ 只小动物，了解到每只小动物是否有崇拜的对象以及具体是谁。现在他想知道每个人能得到的最高票数是多少。

输入描述:

第一行一个正整数  ，代表小动物的数量。
第二行  个以空格分隔的正整数  ，代表每只小动物崇拜的小动物。 
若 ，则代表第  只小动物没有崇拜的对象。
 。
保证 。

输出描述:

共  行，第  行代表第  只小动物可能得到的最多票数。

示例1

输入

4
0 1 1 1

输出

说明

如果第  只小动物均和第一只投一样的票，则第一只小动物可以获得四票。

算法知识视频讲解

Python

O_n2

每个人可以把收到的票投给自己，也可以把自己身上所有的票都寄给崇拜对象。而且，只能崇拜编号比自己小的。

def compute(A, n):
    ticket = [1 for _ in range(n)]
    for i in range(n-1, -1, -1):
        if A[i] > 0:
            ticket[A[i]-1] += ticket[i]
    return ticket

编辑于 2021-04-29 14:58:58 回复(0)