1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

解题思路

题目中每门课至多只有一门直接先修课,并且保证不存在环。因此,所有课程的依赖关系一定构成若干棵树组成的森林。

设一门课程的“深度”为:

  • 没有先修课的课程,深度为 111
  • 如果课程 AAA 的直接先修课是课程 BBB,那么

P4695.第2题-多多的排课

    1000ms Tried: 172 Accepted: 80 Difficulty: 4 所属公司 : 拼多多
    算法与标签>树

题目内容

多多的学校有 nnn 门课程,编号从 111 到 nnn。每门课程可能有一门直接先修课程(或者没有)。如果至少满足以下条件之一,则一门课程 AAA 是另一门课程 BBB 的先修课程:

1.课程 AAA 是课程 BBB 的直接先修课程;

2.课程 BBB 有一门直接先修课程 CCC,且课程 AAA 是课程 CCC 的先修课程;

现在,多多需要安排这些课程的排课计划,将所有 nnn 门课程分配到若干个学期。每个学期中,不能有两门课程 AAA 和 BBB 使得 AAA 是 BBB 的先修课程。问最少需要多少个学期?

输入描述

第一行包含整数 n(1≤n≤2000)n(1≤n≤2000)n(1≤n≤2000)-----课程数量。

接下来 nnn 行,每行包含一个整数 pi(1≤pi≤np_i(1≤p_i≤npi​(1≤pi​≤n 或 pi=−1)p_i=-1)pi​=−1)。第 iii 行的 pip_ipi​ 表示第iii门课程的直接先修课程。如果 pip_ipi​ 为 −1-1−1 ,表示该课程没有先修课程。

输出描述

输出一个整数,表示最少需要的学期数。

补充说明

保证没有课程是自己的直接先修课程 (pi≠i)(pi≠i)(pi=i),也不存在循环依赖。

样例1

输入

5
-1
1
2
1
-1

输出

3

说明

最少需要 333 个学期才能以上述约束排完所有课程,其中的一种排课方式如下:

组 111:课程 1,51,51,5

组 222:课程 2,42,42,4

组 333:课程 333

注:这只是其中的一种排课方式

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 1, 48ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?