luogu#P11501. [ROIR 2019 Day 2] 探险队

    ID: 35373 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>动态规划 DP2019Special Judge树形 DP基环树

[ROIR 2019 Day 2] 探险队

题目背景

翻译自 ROIR 2019 D2T3

题目描述

需要派遣一支探险队前去探索邻近的星系。共有 nn 名候选人,编号从 11nn,探险队成员需要从中选出。

在候选人中进行了一次调查,每个人可以指出一个他不愿意与之一起参加探险的候选人。对于第 ii 个候选人,调查结果是一个整数 aia_{i},表示他不愿意与编号为 aia_i 的人一起参加探险。如果 ii 号候选人愿意与任何人一起参加探险,则 ai=1a_{i} = -1

你需要求出在满足所有派遣出的候选人的意愿的情况下,最大的可以派遣的人数。

输入格式

第一行输入一个整数 nn

接下来 nn 行,每行输入一个整数,分别是 a1,a2,,ana_1,a_2,\dots,a_n

输出格式

输出一个整数,表示最大可以派遣的人数。

4
2
4
2
1
2
3
2
-1
2
2

提示

数据中 Subtask 0 为样例。

子任务 分值 特殊性质
11 1919 n20n\le20
22 1010 a1=1a_1=-1i>1,ai=i1\forall i>1,a_i=i-1
33 1515 ai<ia_i<i
44 1313 1n20001\le n\le2000
55 4343 无特殊性质

对于 100%100\% 的数据,n3×105n\le3\times10^5ai=1a_i=-11ain1\le a_i\le n,且 aiia_i\ne i